perm filename V2R.IN[TEX,DEK] blob sn#336059 filedate 1978-02-20 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00013 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 763 galleys 1-2 NOTE: the end of 1 and beginning of 2 were unreadable.
C00021 00003	folio 768 galley 3
C00039 00004	folio 770 galley 4
C00053 00005	folio 772 galley 5
C00069 00006	folio 776 galley 6
C00085 00007	folio 777 galley 7 WARNING: Couldn't read the beginning of this galley.
C00096 00008	folio 781 galley 8
C00110 00009	folio 784 galley 9
C00129 00010	folio 790 galley 10
C00145 00011	folio 794 galley 11
C00164 00012	folio 797 galley 12
C00182 00013	folio 800 galley 13
C00194 ENDMK
C⊗;
folio 763 galleys 1-2 NOTE: the end of 1 and beginning of 2 were unreadable.
    0  {U0}{H9L11M29}58320#Computer Programming!(Knuth/A.-W.)!ch. 
    2  4!f. 763!g. 1c|'{A24}{H10}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨3|∨
    5  .|∨3|'{A12}{H9}{M21}|∂!!!!!!!|∂!!!!!!!|∂!!!!!!!|∂!!!!!!!|∂|E
    6  |n|;|>|9|1|≡1|≡.|4|927|4α⊗↓|447:|'18|4α⊗↓|442:|;
   10  09|4α⊗↓|405:|;2718|4α⊗↓|44742:|;>|>!!|1|108|4|4|4|4|4|;
   15  04|4|4|4|4|4|;00|4|4|4|4|4|;1269!!|4|;>|>|1|1!!|1|908|1|9|;
   21  04|;00|;!|1|11269|4|4|4|4|4|;>|>|1|1!!15|;14|;
   28  45|;|4|1|1|1|→α_↓0045|4|4|4|4|4|;>|>|1|1!!49|;
   33  16|;45|;0756|;>|>|1|1!!|4|4|4|4|449|;|4|4|4|4|416|;
   40  |4|4|4|4|445|;!!|40756|;>{A4}|>|1|1!!1269|;0756|;
   46  0045|;12888756|;>{A12}|9|1|≡2|≡.|4|9K{H9}|v4|εQ|4α+↓|4|"l|¬K
   49  Q|"L|)|4|¬E|4{H10}|¬K{H9}|v4Q|4α+↓|4|¬KQ|)|4|¬W|4{H10}|¬K{H9
   49  }|v4Q|4α+↓|42|¬KQ|4α+↓|41|)|4α=↓|4|¬K|v4Q|)|4α+↓|41, 
   50  |πso |ε|"l|¬K|v4Q|4α+↓|4R|)|"L|4|¬E|4|"l|¬K|v4Q|)|"L|4α+↓|41
   51  .|'{A3}{H9L11M29}|π|9|1|≡3|≡.|4|9When |εk|4|¬E|42, 
   54  |πthe result is true, so assume that |εk|4|¬Q|42. 
   62  |πLet |εq|βk|4α=↓|42|gQ|rk, r|βk|4α=↓|42|gR|rk, 
   65  |πso that |εR|βk|4α=↓|4|"l|¬K|v4Q|βk|)|"L |πand 
   69  |εQ|βk|4α=↓|4Q|βk|βα_↓|β1|4α+↓|4R|βk|βα_↓|β1. 
   70  |πWe must show that |ε1|4α+↓|4(R|βk|4α+↓|41)2|gR|rk|4|¬E|42|
   74  gQ|rk|rα_↓|r1; |πthis inequality isn't close 
   79  at all, one way is to observe that |ε1|4α+↓|4(R|βk|4α+↓|41)2
   87  |gR|rk|4|¬E|41|4α+↓|42|g2|gR|rk |πand |ε2R|βk|4|¬W|4Q|βk|βα_
   89  ↓|β1 |πwhen |εk|4|¬Q|42. |π(The fact that |ε2R|βk|4|¬W|4Q|βk
   95  |βα_↓|β1 |πis readily proved by induction since 
  102  |εR|βk|βα+↓|β1|4α_↓|4R|βk|4|¬E|41 |πand |εQ|βk|4α_↓|4Q|βk|βα
  104  _↓|β1|4|¬R|42.)|'{A3}|π|9|1|≡4|≡.|4|9For |εj|4α=↓|41,|4.|4.|
  106  4.|4,|4r, |πcalculate |εU|βe(j|g2), jU|βo(j|g2), 
  110  V|βe(j|g2), jV|βo(j|g2); |πand by recursively 
  115  calling the multiplication algorithm, calculate|'
  120  {A9}|h|εW(|→α_↓j)|4|∂α=↓|4(U|βe(j|g2)|4α_↓|4jU|βo(j|g2))(V|β
  120  e(j|g2)|4α_↓|4jV|βo(j|g2));|E|n|;| W(j)|4|Lα=↓|4{H11}({H9}U|
  121  βe(j|g2)|4α+↓|4jU|βo(j|g2){H11})({H9}V|βe(j|g2)|4α+↓|4jV|βo(
  121  j|g2){H11}){H9},>{A4}| W(|→α_↓j)|4|Lα=↓|4{H11}({H9}U|βe(j|g2
  122  )|4α_↓|4jU|βo(j|g2){H11})({H9}V|βe(j|g2)|4α_↓|4jV|βo(j|g2){H
  122  11}){H9};>{A9}|πand then we have |εW|βe(j|g2)|4α=↓|4|f1|d32|
  127  ){H11}({H9}W(j)|4α+↓|4W(|→α_↓j){H11}){H9}, W|βo(j|g2)|4α=↓|4
  128  |f1|d32|){H11}({H9}W(j)|4α_↓|4W(|→α_↓j){H11}){H9}. 
  129  |πAlso calculate |εW|βe(0)|4α=↓|4U(0)V(0). |πNow 
  133  construct di=erence tables for |εW|βe |πand |εW|βo, 
  140  |πwhich are polynomials whose respective degrees 
  146  are |εr |πand |εr|4α_↓|41.|'|π!!|1|1This method 
  152  reduces the size of the numbers being handled, 
  160  and reduces the number of additions and multiplications. 
  168  Its only disadvantage is a longer program (since 
  176  the control is somewhat more complex, and some 
  184  of the calculations must be done with signed 
  192  numbers).|'{H9L11M29}!!|1|1Another possibility 
  195  would perhaps be to evaluate |εW|βe |πand |εW|βo 
  203  |πat 1|g2, 2|g2, 4|g2,|4.|4.|4.|4, (2|ε|gr)|g2; 
  208  |πalthough the numbers involved are larger, the 
  215  calculations are faster, since all multiplications 
  221  are replaced by shifting and all divisions are 
  229  by binary numbers of the form |ε2|gj(2|gk|4α_↓|41). 
  236  (|πSimple procedures are available for dividing 
  242  by such numbers.)|'{A3}|π|9|1|≡5|≡.|9|4Start 
  246  the |εq, r |πsequences out with |εq|β0, q|β1 
  254  |πlarge enough so that the inequality in exercise 
  262  3 is valid. Then we will _nd in the formulas 
  272  analogous to those preceding Theorem C that |ε|≤h|β1|4|¬M|40
  279   |πand |ε|≤h|β2|4α=↓|4(1|4α+↓|41/2r|βk)2|ur1|4α+↓|4|¬H2Q|βkα
  281  _↓|¬H2Q|βk|βα+↓|β1|)|)(Q|βk/Q|βk|βα+↓|β1). |πThe 
  283  factor |εQ|βk/Q|βk|βα+↓|β1|4|¬M|41 |πas |εk|4|¬M|4|¬X, 
  287  |πso we can ignore it if we want to show |ε|≤h|β2|4|¬W|41|4α
  297  _↓|4|≤e |πfor all large |εk. |πNow |ε|¬H|v42Q|βk|βα+↓|β1|)|4
  303  α=↓|4{H10}|¬H{H9}|v42Q|βk|4α+↓|42|"p|¬H2Q|βk|"P|4α+↓|42|)|4|
  303  ¬R|4{H10}|¬H{H9}|v4(2Q|βk|4α+↓|42|¬H2Q|βk|4α+↓|41)|4α+↓|41|4
  303  |¬R|4|¬H2Q|βk|4α+↓|41|4α+↓|41/3R|βk. |πHence 
  305  |ε|≤h|β2|4|¬E|4(1|4α+↓|41/2r|βk)2|gα_↓|g1|g/|g3|gR|rk, 
  306  |πand lg |ε|≤h|β2|4|¬W|40 |πfor large enough 
  312  |εk.|'!!|1|1Note|*/: |\|πAlgorithm C can also 
  318  be modi_ed to de_ne a sequence |εq|β0, q|β1,|4.|4.|4. 
  326  |πof a similar type which is based on |εn, |πso 
  336  that |εn|4|¬V|4q|βk|4α+↓|4q|βk|βα+↓|β1 |πafter 
  339  step C1. (Algorithm S essentially does this.) 
  346  This would establish (19).|'{A3}{A3}{H9L11M29}|9|1|≡6|≡.|9|4
  350  Any common divisor of |ε6q|4α+↓|4d|β1 |πand |ε6q|4α+↓|4d|β2 
  357  |πmust also divide their di=erence |εd|β2|4α_↓|4d|β1. 
  363  |πThe (|f6|d52|)) di=erences are 2, 3, 4, 6, 
  371  8, 1, 2, 4, 6, 1, 3, 5, 2, 4, 2, |πso we must 
  385  only show that at most one of the given numbers 
  395  is divisible by each of the primes 2, 3, 5. Clearly 
  406  only |ε6q|4α+↓|42 |πis even, and only |ε6q|4α+↓|43 
  413  |πis a multiple of 3; and there is at most one 
  424  multiple of 5, since |εq|βk|4|=|↔6|"o|43 (|πmodulo 
  430  5).|'{A3}|9|1|≡7|≡.|9|4|εt|βk|4|¬E|46t|βk|βα_↓|β1|4α+↓|4ck3|
  431  gk |πfor some constant |εc; |πso |εt|βk/6|gk|4|¬E|4t|βk|βα_↓
  437  |β1/6|gk|gα_↓|g1|4α+↓|4ck/2|gk|4|¬E|4t|β0|4α+↓|4c|4|¬K|ur|)j
  437  |¬R1|4(j/2|gj)|4α=↓|4M. |πThus |εt|βk|4|¬E|4M|4|¬O|46|gk.|'
  440  {A3}|π|9|1|≡8|≡.|4|9The analog of Eq. (39) would 
  446  break down. In fact it is impossible to ``untransform'' 
  455  the _nite Fourier transform of (|εa|β0, a|β1, 
  462  a|β2, a|β3) |πmod 15 when |ε|≤v|4α=↓|42, |πsince 
  469  information is lost during the transformation 
  475  process.|'{A3}|9|1|≡9|≡.|9|4|εKu|ur|)(|→α_↓r)|4|πmod|4|εK|).
  476  |'{A3}|π|≡1|≡0|≡.|4|9The lower bound ensures 
  481  that |ε|λ3|4α+↓|42|4|¬W|4n, |πso the products 
  486  |ε|=#U|βt|=#V|βt |πhave fewer bits than the product 
  493  |εuv. |πThe upper bound comes from the de_nition 
  501  of |ε|≤v. |π[Sch|=4onhage observes that we could 
  508  actually allow |εk|4α=↓|4|λ3|4α+↓|44, |πsince 
  512  |ε(2|g3|g|¬O|g2|in|iα_↓|i2|4α_↓|42|g2|in|iα_↓|i2)|g2|4|"o|42
  512  |4(|πmodulo 2|g2|i|εn|4α+↓|41).]|'{A3}|π|≡1|≡1|≡.|4|9An 
  515  automaton cannot have |εz|β2|4α=↓|41 |πuntil 
  520  it has |εc|4|¬R|42, |πand this occurs _rst for 
  528  |εM|βj |πat time |ε3j|4α_↓|41. |πIt follows that 
  535  |εM|βj |πcannot have |εz|β2z|β1z|β0|4|=|↔6α=↓|4000 
  539  |πuntil time |ε3(j|4α_↓|41). |πFurthermore, if 
  544  |εM|βj |πhas |εz|β0|4|=|↔6α=↓|40 |πat time |εt, 
  550  |πwe cannot change this to |εz|β0|4α=↓|40 |πwithout 
  557  a=ecting the output; but the output cannot be 
  565  a=ected by this value of |εz|β0 |πuntil at least 
  574  time |εt|4α+↓|4j|4α_↓|41, |πso we must have |εt|4α+↓|4j|4α_↓
  580  |41|4|¬E|42n. |πSince the _rst argument we gave 
  587  proves that |ε3(j|4α_↓|41)|4|¬E|4t, |πwe must 
  592  have |ε4(j|4α_↓|41)|4|¬E|42n, |πthat is, |εj|4α_↓|41|4|¬E|4n
  596  /2, |πi.e., |εj|4|¬E|4|"ln/2|"L|4α+↓|41.|'|π!!|1|1Furthermor
  599  e, this is the best possible bound, since the 
  608  inputs |εu|4α=↓|4v|4α=↓|42|gn|4α_↓|41 |πrequire 
  611  the use of |εM|βj |πfor all |εj|4|¬E|4|"ln/2|"L|4α+↓|41. 
  618  |π(For example, note from Table 1 that |εM|β2 
  626  |πis needed to multiply two-bit numbers, at time 
  634  3.)|'{A3}*?|≡1|≡3|≡.|9|4If it takes |εT(n) |πcycles 
  640  to multiply |εn-|πbit numbers, we can accomplish 
  647  the multiplication of |εm-|πbit by |εn-|πbit 
  653  by breaking the |εn-|πbit number into |"p|εn/m|"P 
  660  m-|πbit groups, using |ε|"pn/m|"PT(m)|4α+↓|4O(n|4α+↓|4m) 
  664  |πoperations. The results of this section therefore 
  671  give an estimated running time of |εO(n|4|πlog|4|εm|4|πlog|4
  677  log|4|εm).|'{A24}{H10L12M29}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|1|∨4|∨
  678  .|∨4|'{A12}{H9L11M29}|9|1|≡1|≡.|4|9We compute 
  681  {H11}({H9}|¬O|4|¬O|4|¬O|4(|εa|βmb|βm|βα_↓|β1|4α+↓|4a|βm|βα_↓
  681  |β2)b|βm|βα_↓|β2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|β1{H11}){H9
  681  }b|β1|4α+↓|4a|β0 |πby adding and multiplying 
  686  in the |εB|βj-|πsystem.|'{A9}{M25.6}|∂!!!!!!!!!|∂!!|∂!!!!!!|
  689  ∂!!!!!|∂!!!!!|∂!!!!!!!|∂|E|;|>|;T.|;α=↓|420(cwt.|;
  694  α=↓|48(st.|;α=↓|414(lb.|;α=↓|416|4oz.)))|;>{A2}|>
  699  Start|4with|4zer|>Divide|4by|4|¬X|'0|;0|;|9|10|;
  704  |9|10|;Remainder|4α=↓|48|;>{A12}|εAnswer|*/: |\|π8|4T. 
  709  3|4cwt. 1|4st. 2|4lb. 5|4oz.|'{A3}|9|1|≡3|≡.|9|4[|εCACM 
  714  |≡2|≡, 7 (|πJuly, 1959), 27.]|'{I3.2H}{H9L11M29}!!|1|1(Note|
  719  */:|\ |πIt is possible for this algorithm to yield 
  728  |εU|4α=↓|41; |πif this is undesirable, we could 
  735  modify the algorithm as follows: In step A1, 
  743  set a new variable |εt|4|¬L|41. |πIn step A2, 
  751  do not go to A4 if |εt|4α=↓|41. |πIn step A3, 
  761  set |εt|4|¬L|40 |πif |εU|βα_↓|βk|4|=|↔6α=↓|4B|4α_↓|41. 
  765  |πThe re{A9}|ε1/10|4α_↓|42|gα_↓|g3|g5|4|¬W|4|≤a|4α=↓|4(.0001
  766  10011001100110011001100110011)|β2|4|¬W|41/10,|;
  767  {A9}|πwe _nd that |ε|≤au|4α_↓|4|≤e|4|¬E|4v|4|≤E|4|≤au 
  771  |πat the end of the computation, where|'{A9}|ε|≤e|4α=↓|4|f7|
  778  d38|)|4α+↓|4(.100010001010100011001000101010001)|β2|4|¬W|4|f
  778  3|d32|).|;{A9}|πHence |εu/10|4α_↓|42|4|¬W|4u/10|4α_↓|4{H11}(
  780  {H9}|≤e|4α+↓|4(1/10|4α_↓|4|≤a)u{H11}){H9}|4|¬E|4v|4|¬E|4|≤au
  780  |4|¬W|4u/10. |πSince |εv |πis an integer, the 
  787  proof is complete.|'{A3}|≡1|≡0|≡.|4|9(a) Shift 
  792  right one; (b) Extract left bit of each group; 
  801  (c) Shift result of (b) right two; (d) Shift 
  810  result of (c) right one, and add to result of 
  820  (c); (e) Subtract result of d from result of 
  829  (a).|'{A3}|h|π11.|9|4|∂|→α_↓|4|1|∂o0o0o0|E|n|'
  831  |≡1|≡1|≡.|L|L5.7|4|17|4|12|4|11>|L|→α_↓|4|11|4|10>
  833  {A4}|L|L4|4|17.7|4|12|4|11>|L|→α_↓|4|1|9|1|1|49|4|14>
  835  {A4}|L|L3|4|18|4|13.2|4|11>|L|→α_↓|4|1|9|1|1|47|4|16|4|16>
  837  {A4}|L|L3|4|10|4|16|4|16.1>|L|→α_↓|9|1|1|46|4|11|4|13|4|12>
  839  {A4}|L|L2|4|14|4|15|4|12|4|19!!|εAnswer|*/:|4|1|\|π(24529)|β1
  839  |β0.|'{A3}{H9L11M29}|≡1|≡2|≡.|9|4First convert 
  842  the ternary number to nonary (radix 9) notation, 
  850  then proceed as in octal-to-decimal conversion 
  856  but without doubling. Decimal to nonary is similar. 
  864  In the given example, we have|'{A12}|h|π|→α_↓|4|1|∂poikiop|E
  870  |n|'|L1.7|4|16|4|14|4|17|4|12|4|13>|→α_↓|1|4|1|9|1|41>
  873  {A4}|L1|4|16.6|4|14|4|17|4|12|4|13>|→α_↓|4|1|1|9|1|41|4|16>
  875  {A4}|L1|4|15|4|10.4|4|17|4|12|4|13>|→α_↓|1|4|1|9|1|41|4|15|4
  876  |10>{A4}|L1|4|13|4|15|4|14.7|4|12|4|13>|→α_↓|1|9|1|4|1|41|4|
  878  13|4|15|4|14>{A4}|L1|4|12|4|11|4|19|4|13.2|4|13>
  880  |→α_↓|1|9|1|4|1|41|4|12|4|11|4|19|4|13>{A4}|L1|4|10|4|19|4|1
  881  7|4|13|4|19.3>|→α_↓|1|9|1|4|1|41|4|10|4|19|4|17|4|13|4|19>
  883  {A4}|L|1|9|1|49|4|18|4|17|4|16|4|15|4|14!!|εAnswer|*/:|4|1|\|
  883  π(987654)|β1|β0.|'{A12}|L|1|9|1|49.8|4|17|4|16|4|15|4|14>
  885  |→α+↓|4|1|9|1|9|1|1|4|1|49|'{A4}|L1|4|11|4|18.7|4|16|4|15|4|
  886  14>|→α+↓|1|4|1|9|1|41|4|11|4|18|'{A4}|L1|4|13|4|11|4|16.6|4|
  888  15|4|14>|→α+↓|1|4|1|9|1|41|4|13|4|11|4|16|'{A4}|L1|4|14|4|14
  890  |4|18|4|13.5|4|14>|→α+↓|4|1|1|9|4|11|4|14|4|14|4|18|4|13|'
  892  {A4}|L1|4|16|4|10|4|14|4|12|4|18.4>|→α+↓|1|4|1|9|1|41|4|16|4
  893  |10|4|14|4|12|4|18|'{A4}|L1|4|17|4|16|4|14|4|17|4|12|4|13!!|
  894  εAnswer|*/:|4|1|\|π(1764723)|β9.|'{A12}{H9L11M29}|H*?{U0}{H10L
folio 768 galley 3
  895  12M29}58320#Computer Programming!(Knuth/A.-W.)!f. 
  897  768!ch. 4!g. 3c|'{A12}{H9L11M29}|∂!!|1|1|∂!!!!|∂!!!!|∂!!!!!!
  900  !!!!!!!|∂!!!!!!!!!!!!!!!|9|1|∂|E|;|>|≡1|≡3|≡.|'
  903  |¬b|¬u|¬f|¬1|'|¬a|¬l|¬f|'.|'(Radix|4point|4on|4_rst|4line)|'
  907  >|>|;|;|¬o|¬r|¬i|¬g|'|9|1|1|≤%|¬2|¬3|'|;>|>|;
  917  |¬b|¬f|¬2|'|¬o|¬r|¬i|¬g|'|9|1|1|≤%|¬2|¬4|'>|>
  922  |;|¬s|¬t|¬a|¬r|¬t|'|¬j|¬o|¬v|'|¬o|¬f|¬l|¬o|'Ensure|4over⊗ow|
  926  4is|4o=.|'>|>|;|;|¬e|¬n|¬t|¬2|'|¬b|¬u|¬f|¬1|¬-|¬b|¬u|¬f|¬2|'
  933  Set|4bu=er|4pointer.|'>|>|;|¬8|¬h|'|¬e|¬n|¬t|¬3|'
  939  |¬1|¬0|'Set|4loop|4counter.|'>|>|;|¬1|¬h|'|¬e|¬n|¬t|¬1|'
  946  |εm|'|πBegin|4multiplication|4routine.|'>|>|;
  951  |;|¬e|¬n|¬t|¬x|'|¬0|'>|>|;|¬2|¬h|'|¬s|¬t|¬x|'
  959  |¬c|¬a|¬r|¬r|¬y|'>|>|;|;.|4.|4.|'|;(See|4exercise|44.3.1<13,
  966  |4with|'>|>|;|;|¬j|¬i|¬p|'|¬2|¬b|'!|εv|4α=↓|410|g9|4|πand|4|
  973  ¬w|4α=↓|4|¬u.)|'>|>|;|;|¬s|¬l|¬a|¬x|'|¬5|'rA|4|¬M|4next|4nin
  980  e|4digits.|'>|>|;|;|¬c|¬h|¬a|¬r|'|;|;>|>|;|;|¬s|¬t|¬a|'
  993  |¬b|¬u|¬f|¬2|¬,|¬2|≤#|¬2|¬.|¬5|≤#|'Store next|4nine|4digits.
  995  |'>|>|;|;|¬s|¬t|¬x|'|¬b|¬u|¬f|¬2|≤%|¬1|¬,|¬2|'
 1002  >|>|;|;|¬i|¬n|¬c|¬2|'|¬2|'Increase|4bu=er|4pointer.|'
 1009  >|>|;|;|¬d|¬e|¬c|¬3|'|¬1|'>|>|;|;|¬j|¬3|¬p|'|¬1|¬b|'
 1021  Repeat|4ten|4times.|'>|>|;|;|¬o|¬u|¬t|'|¬b|¬u|¬f|¬2|¬-|¬2|¬0
 1027  |¬,|¬2|≤#|¬p|¬r|¬i|¬n|¬t|¬e|¬r|≤&|'>|>|;|;|¬j|¬2|¬p|'
 1033  |¬d|¬o|¬n|¬e|'Have|4we|4printed|4both|4lines?|'
 1035  >|>|;|;|¬e|¬n|¬t|¬2|'|¬0|'Set|4bu=er|4pointer|4for|42nd|4bu=
 1041  er.|'>|>|;|;|¬j|¬m|¬p|'|¬8|¬b|'>{A3}{H9L11M29}|≡1|≡4|≡.|4|9L
 1049  et |εK(n) |πbe the number of steps required to 
 1058  convert an |εn-|πdigit decimal number to binary 
 1065  and at the same time to compute the binary representation 
 1075  of 10|g|εn. |πThen we have |εK(2n)|4|¬E|42K(n)|4α+↓|4O{H11}(
 1080  {H9}M(n){H11}){H9}. Proof|*/: |\|πGiven the number 
 1085  |εU|4α=↓|4(u|β2|βn|βα_↓|β1|4.|4.|4.|4u|β0)|β1|β0, 
 1086  |πcompute |εU|β1|4α=↓|4(u|β2|βn|βα_↓|β1|4.|4.|4.|4u|βn)|β1|β
 1087  0 |πand |εU|β0|4α=↓|4(u|βn|βα_↓|β1|4.|4.|4.|4u|β0)|β1|β0 
 1090  |πand 10|ε|gn, |πin |ε2K(n) |πcycles, then compute 
 1097  |εU|4α=↓|410|gnU|β1|4α+↓|4U|β0 |πand |ε10|g2|gn|4α=↓|410|gn|
 1099  4|¬O|410|gn |πin |εO{H11}({H9}M(n){H11}){H9} 
 1102  |πcycles. It follows that |εK(2|gn)|4α=↓|4O{H11}({H9}M(2|gn)
 1106  |4α+↓|42M(2|gn|gα_↓|g1)|4α+↓|44M(2|gn|gα_↓|g2)|4α+↓|4|¬O|4|¬
 1106  O|4|¬O{H11}){H9}|4α=↓|4O{H11}({H9}nM(n){H11}){H9}.|'
 1107  {H9L11M29}|π!!|1|1(Similarly, Sch|=4onhage has 
 1110  observed that we can convert a (2|ε|gn|4|πlg|β2 
 1117  10)-bit number |εU |πfrom binary to decimal, 
 1124  in |εO{H11}({H9}nM(2|gn){H11}){H9} |πsteps. First 
 1128  form |εV|4α=↓|410|g2|in|iα_↓|i1 |πin |εO{H11}({H9}M(2|gn|gα_
 1131  ↓|g1)|4α+↓|4M(2|gn|gα_↓|g2)|4α+↓|4|¬O|4|¬O|4|¬O{H11}){H9}|4α
 1131  =↓|4O{H11}({H9}M(2|gn)) |πsteps, then compute 
 1135  |εU|β0|4α=↓|4(U |πmod |εV) |πand |εU|β1|4α=↓|4|"lU/V|"L 
 1140  |πin |εO{H11}({H9}M(2|gn)) |πfurther steps, then 
 1145  convert |εU|β0 |πand |εU|β1.)|'{A3}|π|≡1|≡8|≡.|4|9Let 
 1150  |εU|4α=↓|4|πround|ε|βB(u,|4P) |πand |εv|4α=↓|4|πround|ε|βb(U
 1152  ,|4p). |πWe may assume that |εu|4|=|↔6α=↓|40, 
 1158  |πso that |εU|4|=|↔6α=↓|40 |πand |εv|4|=|↔6α=↓|40. 
 1163  Case |*/|↔O|\ v|4|¬W|4u: |πDetermine |εe |πand 
 1169  |εE |πsuch that |εb|ge|gα_↓|g1|4|¬W|4u|4|¬E|4b|ge, 
 1173  B|gE|gα_↓|g1|4|¬E|4U|4|¬W|4B|gE. |πThen |εu|4|¬E|4b|gp|gα_↓|
 1175  geu|4|¬E|4U|4α+↓|4|f1|d32|)B|gE|gα_↓|gP |πand 
 1177  |εU|4|¬E|4u|4α_↓|4|f1|d32|)b|ge|gα_↓|gp; |πhence 
 1179  |εB|gP|gα_↓|g1|4|¬E|4B|gP|gα_↓|gEU|4|¬W|4B|gP|gα_↓|gEu|4|¬E|
 1179  4b|gp|gα_↓|geu|4|¬E|4b|gp. Case |*/|↔P|\, v|4|¬Q|4u: 
 1183  |πDetermine |εe |πand |εE |πsuch that |εb|ge|gα_↓|g1|4|¬E|4u
 1189  |4|¬W|4b|ge, B|gE|gα_↓|g1|4|¬W|4U|4|¬E|4B|gE. 
 1191  |πThen |εu|4|¬R|4U|4α_↓|4|f1|d32|)B|gE|gα_↓|gP 
 1193  |πand |εU|4|¬R|4u|4α+↓|4|f1|d32|)b|ge|gα_↓|gp; 
 1195  |πhence |εB|gP|gα_↓|g1|4|¬E|4B|gP|gα_↓|gE(U|4α_↓|4B|gE|gα_↓|
 1196  gP)|4|¬W|4B|gP|gα_↓|gEu|4|¬E|4b|gp|gα_↓|geu|4|¬W|4b|gp. 
 1197  |πThus we have proved that |εB|gP|gα_↓|g1|4|¬W|4b|gp 
 1203  |πwhenever |εv|4|=|↔6α=↓|4u.|'|π!!|1|1Conversely, 
 1206  if |εB|gP|gα_↓|g1|4|¬W|4b|gp, |πthe above proof 
 1211  suggests that the most likely example for which 
 1219  |εu|4|=|↔6α=↓|4v |πwill occur when |εu |πis a 
 1226  power of |εb |πand at the same time it is close 
 1237  to a power of |εB. |πWe have |εB|gP|gα_↓|g1b|gp|4|¬W|4B|gP|g
 1244  α_↓|g1b|gp|4α+↓|4|f1|d32|)b|gp|4α_↓|4|f1|d32|)B|gP|gα_↓|g1|4
 1244  α_↓|4|f1|d34|)|4α=↓|4(B|gP|gα_↓|g1|4α+↓|4|f1|d32|))|4α⊗↓|4(b
 1244  |gp|4α_↓|4|f1|d32|)); |πhence |ε1|4|¬W|4|≤a|4α=↓|41/(1|4α_↓|
 1246  4|f1|d32|)b|gα_↓|gp)|4|¬W|41|4α+↓|4|f1|d32|)B|g1|gα_↓|gP|4α=
 1246  ↓|4|≤b. |πThere are integers |εe |πand |εE |πsuch 
 1254  that log|ε|βB|4|≤a|4|¬W|4e|4|πlog|ε|βB|4b|4α_↓|4E|4|¬W|4|πlo
 1255  g|ε|βB|4|≤b, |πsince Weyl's theorem (exercise 
 1260  3.5<22) implies that there is an integer |εe 
 1268  |πwith |ε0|4|¬W|4|πlog|ε|βB|4|≤a|4|¬W|4(e|4|πlog|ε|βB)|πmod|
 1269  41|4|¬W|4log|ε|βB|4|≤b|4|¬W|41 |πwhen log|ε|βB|4b 
 1272  |πis irrational. Hence |ε|≤a|4|¬W|4b|ge/B|gE|4|¬W|4|≤b, 
 1276  |πfor some |εe |πand |εE. |π(Such |εe |πand |εE 
 1285  |πmay also be found by applying the theory of 
 1294  continued fractions, see Section 4.5.3.) Now 
 1300  we have round|ε|βB(b|ge,|4P)|4α=↓|4B|gE, |πand 
 1304  round|ε|βb(B|gE,|4p)|4|¬W|4b|ge. [CACM |≡1|≡1 
 1307  (1968), 47<50; |εProc. Amer. Math. Soc. |≡1|≡9 
 1314  (1968), 716<723.]|'{A3}|π|≡1|≡9|≡.|4|9|εm|β1|4α=↓|4|≤#|¬f|¬o
 1316  |¬f|¬o|¬f|¬o|¬f|¬o|≤&|β1|β6, c|β1|4α=↓|41|4α_↓|410/16 
 1318  |πmakes |εU|4α=↓|4{H11}({H9}(u|β7u|β6)|β1|β0|4.|4.|4.|4(u|β1
 1319  u|β0)|β1|β0{H11}){H9}|β2|β5|β6; m|β2|4α=↓|4|≤#|¬f|¬f|¬o|¬o|¬
 1320  f|¬f|¬o|¬o|≤&|β1|β6, c|β2|4α=↓|41|4α_↓|410|g2/16|g2 
 1322  |πmakes |εU|4α=↓|4{H11}({H9}(u|β7u|β6u|β5u|β4)|β1|β0(u|β3u|β
 1323  2u|β1u|β0)|β1|β0{H11}){H9}|β6|β5|β5|β3|β6; m|β3|4α=↓|4|≤#|¬f
 1324  |¬f|¬f|¬f|¬o|¬o|¬o|¬o|≤&|β1|β6; c|β3|4α=↓|41|4α_↓|410|g4/16|
 1325  g4. |π(Cf. exercise 14. This technique is due 
 1333  to Roy A. Keir, circa 1958.)|'{A24}{H10L12M29}|∨S|∨E|∨C|∨T|∨
 1339  I|∨O|∨N|9|∨4|∨.|∨5|∨.|∨1|'{A12}{H9L11M29}|9|1|≡1|≡.|4|9Test 
 1341  whether or not |εuv|¬S|4|¬W|4u|¬Sv, |πsince the 
 1347  denominators are positive.|'{A3}|9|1|≡2|≡.|4|9If 
 1351  |εc|4|¬Q|41 |πdivides both |εu/d |πand |εv/d, 
 1357  |πthen |εcd |πdivides both |εu |πand |εv.|'{A3}|π|1|9|≡3|≡.|
 1364  4|9Let |εp |πbe prime. If |εp|ge |πis a divisor 
 1373  of |εuv |πand |εu|¬Sv|¬S |πfor |εe|4|¬R|41, |πthen 
 1380  either |εp|ge|¬Du |πand |εp|ge|¬Dv|¬S |πor |εp|ge|¬Du|¬S 
 1386  |πand |εp|ge|¬Dv; |πhence |εp|ge|¬D|πgcd(|εu,|4v|¬S) 
 1390  |πgcd(|εu|¬S,|4v). |πThe converse follows by 
 1395  reversing the argument.|'{A3}|9|1|≡4|≡.|9|4Let 
 1399  |εd|β1|4α=↓|4|πgcd(|εu,|4v), d|β2|4α=↓|4|πgcd(|εu|¬S,|4v|¬S)
 1400  ; |πthe answer is |εw|4α=↓|4(u/d|β1)(v|¬S/d|β2) 
 1405  |πsign(|εv), w|¬S|4α=↓|4|¬G(u|¬S/d|β2)(v/d|β1)|¬G, 
 1407  |πwith a ``divide by zero'' error message if 
 1415  |εv|4α=↓|40.|'{A3}|1|9|≡5|≡.|4|9d|β1|4α=↓|410, 
 1417  t|4α=↓|417|4|¬O|47|4α_↓|427|4|¬O|412|4α=↓|4|→α_↓205, 
 1418  d|β2|4α=↓|45, w|4α=↓|4|→α_↓41, w|¬S|4α=↓|4168.|'
 1421  {A3}|π|1|9|≡6|≡.|4|9Let |εu|¬C|4α=↓|4u|¬S/d|β1, 
 1423  v|¬C|4α=↓|4v|¬S/d|β1; |πwe want to show that 
 1429  gcd(|εuv|¬C|4α+↓|4u|¬Cv,|4d|β1)|4α=↓|4|πgcd(|εuv|¬C|4α+↓|4u|
 1429  ¬Cv, d|β1u|¬Cv|¬C). |πIf |εp |πis a prime which 
 1437  divides |εu|¬C, |πthen |εp |πdoes not divide 
 1444  |εu |πor |εv|¬C, |πsp |εp |πdoes not divide |εuv|¬C|4α+↓|4u|
 1452  ¬Cv. |πA similar argument holds for prime divisors 
 1460  of |εv|¬C, |πso no prime divisors of |εu|¬Cv|¬C 
 1468  |πa=ect the given gcd.|'{A3}|9|1|≡7|≡.|9|4(|εN|4α_↓|41)|g2|4
 1472  α+↓|4(N|4α_↓|42)|g2|4α=↓|42N|g2|4α_↓|4(6N|4α_↓|45). 
 1473  |πIf the inputs are |εn-|πbit binary numbers, 
 1480  |ε2n|4α+↓|41 |πbits may be necessary to represent 
 1487  |εt.|'{A3}|9|1|≡8|≡.|4|9|πFor multiplication 
 1490  and division these quantities will obey the rules 
 1498  |εx/0|4α=↓|4|πsign(|εx)|¬X, (|¬N|¬X)|4α⊗↓|4x|4α=↓|4x|4α⊗↓|4(
 1499  |→|¬N|¬X)|4α=↓|4(|→|¬N|¬X)/x|4α=↓|4|¬N|πsign(|εx)|¬X, 
 1500  x/(|→|¬N|¬X)|4α=↓|40, |πprovided that |εx |πis 
 1505  _nite and nonzero, without change to the algorithms 
 1513  described. Furthermore, the algorithms can readily 
 1519  be modi_ed so that 0/0|4α=↓|40|4α⊗↓|4(|→|¬N|¬X)|4α=↓|4(|→|¬N
 1523  |¬X)|4α⊗↓|40|4α=↓|4``(0/0)'', where the latter 
 1527  is a representation of ``unde_ned''; and so that 
 1535  if either operand is ``unde_ned'' the result 
 1542  will be ``unde_ned'' also. Since the multiplication 
 1549  and division subroutines can yield these fairly 
 1556  natural rules of ``extended arithmetic,'' it 
 1562  is sometimes worth while to modify the addition 
 1570  and subtraction operations so that they satisfy 
 1577  the rules |εx|4|¬N|4|¬X|4α=↓|4|→|¬N|¬x, x|4|¬N|4(|→α_↓|¬X)|4
 1580  α=↓|4|→|"c|¬x, |πfor |εx |π_nite; (|¬N|¬X)|4α+↓|4(|→|¬N|¬X)|
 1584  4α=↓|4|→|¬N|¬X|4α_↓|4(|→|"c|¬X)|4α=↓|4|→|¬N|¬X, 
 1585  (|→|¬N|¬X)|4α+↓|4(|→|"c|¬X)|4α=↓|4(|→|¬n|¬x)|4α_↓|4(|→|¬N|¬X
 1585  )|4α=↓|4(0/0); and if either or both operands 
 1592  is (0/0), so is the result. Equality tests and 
 1601  comparisons may be treated in a similar manner.|'
 1609  !!|1|1The above remarks are independent of ``over⊗ow'' 
 1616  indications. If |¬X is being used to suggest 
 1624  over⊗ow, it is incorrect to let 1/|¬x be equal 
 1633  to zero, or to let |¬X|4α_↓|4|¬X be equal to 
 1642  zero, lest inaccurate results be regarded as 
 1649  true answers*3 It is far better to represent over⊗ow 
 1658  by (0/0), and to use the convention that the 
 1667  result of any operation is unde_ned if at least 
 1676  one of the inputs is unde_ned. This type of over⊗ow 
 1686  indication has the advantage that _nal results 
 1693  of an extended calculation reveal exactly which 
 1700  answers are de_ned and which are not.|'{A3}|9|1|≡9|≡.|4|9If 
 1708  |εu/u|¬S|4|=|↔/α=↓|4v/v|¬S, |πthen|'{A9}|ε1|4|¬E|4|¬Guv|¬S|4
 1710  α_↓|4u|¬Sv|¬G|4α=↓|4u|¬Sv|¬S|¬G(u/u|¬S)|4α_↓|4(v/v|¬S)|¬G|4|
 1710  ¬W|4|¬G2|g2|gn(u/u|¬S)|4α_↓|42|g2|gn(v/v|¬S)|¬G;|;
 1711  {A9}|πtwo quantities di=ering by more than unity 
 1718  cannot have the same ``⊗oor.'' {H11}({H9}In other 
 1725  words, the _rst |ε2n |πbits to the right of the 
 1735  binary point is enough to characterize the value 
 1743  of the fraction, when there are |εn-|πbit denominators. 
 1751  We cannot improve this to |ε2n|4α_↓|41 |πbits, 
 1758  for if |εn|4α=↓|44 |πwe have |f1|d313|)|4α=↓|4(.00010011|4.|
 1763  4.|4.)|β2, |f1|d314|)|4α=↓|4(.00010010|4.|4.|4.)|β2.{H11}){H
 1764  9}|'{A3}|π|≡1|≡1|≡.|4|9To divide by |ε(v|4α+↓|4v|¬S|¬H|v45|)
 1768  )/v|¬C, |πwhen |εv |πand |εv|¬S |πare not both 
 1776  zero, multiply by{U0}{H10L12M29}58320#Computer 
folio 770 galley 4
 1779  Programming!(Knuth/A.-W.)!f. 770!ch. 4!g. 4c|'
 1783  {A24}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨5|∨.|∨2|'
 1784  {A12}{H9L11M29}|9|1|≡1|≡.|4|9Substitute min, 
 1786  max, α+↓ consistently for gcd, lcm, α⊗↓.|'{A3}|9|1|≡2|≡.|4|9
 1793  For prime |εp, |πlet |εu|βp, v|β1|mp,|4.|4.|4.|4,|4v|βn|βp 
 1799  |πbe the exponents of |εp |πin the canonical 
 1807  factorization of |εu, v|β1,|4.|4.|4.|4,|4v|βn. 
 1811  |πBy hypothesis, |εu|βp|4|¬E|4v|β1|βp|4α+↓|1|1|¬O|4|¬O|4|¬O|
 1813  1|1α+↓|4v|βn|βp. |πWe must show that |εu|βp|4|¬E|4|πmin(|εu|
 1818  βp,|4v|β1|βp)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4|πmin(|εu|βp,|4v
 1818  |βn|βp), |πand this is certainly true if |εu|βp 
 1826  |πis greater than or equal to each |εv|βj|βp, 
 1834  |πor if |εu|βp |πis less than some |εv|βj|βp.|'
 1842  {A3}|1|9|≡3|≡.|4|9Solution |*/|↔O: |\|πA one-to-one 
 1846  correspondence is obtained if we set |εu|4α=↓|4|πgcd(|εd,|4n
 1852  ), v|4α=↓|4n|g2/|πlcm(|εd,|4n) |πfor each divisor 
 1857  |εd |πof |εn|g2. Solution |*/|↔P: |\|πIf |εn|4α=↓|4p|ure|)1|g
 1863  1|)|4.|4.|4.|4p|ure|)r|gr|), |πthe number in 
 1867  each case is |ε(2e|β1|4α+↓|41)|4.|4.|4.|4(2e|βr|4α+↓|41).|'
 1871  {A3}|π|≡4|≡.|4|9See exercise 3.2.1.2<15(a).|'
 1874  {A3}|1|9|≡5|≡.|4|9Shift |εu, v |πright until 
 1879  neither is a multiple of 3; each iteration sets 
 1888  |εt|4|¬L|4u|4α+↓|4v |πor |εt|4|¬L|4u|4α_↓|4v 
 1891  (|πwhichever is a multiple of 3), and shifts 
 1899  |εt |πright until it is not a multiple of 3, 
 1909  then replaces max|ε(u,|4v) |πby the result.|'
 1915  {A9}|∂|9|1|9|1|9|1|9|1|9|1|∂|9|1|9|1|9|1|9|1|9|1|∂|9|1|9|1|9
 1915  |1|9|1|9|1|4|1|4|1|9|1|9|1|9|1|9|1|4|1|4|1|9|1|9|1|9|1|9|1|4
 1915  |1|1|∂|E|;|>|εu|;!!!!v|;!!!!t|;>{A3}|>13634|?
 1923  !!!!24140|?!!!!10506,|4|13502;|'>|>13636|?!!!!3502|?
 1929  !!!!17136,|4|15712,|4|11904;|'>|>1904|?!!!!3502|?
 1934  !!!!5406,|4|11802;|'>|>1904|?!!!!1802|?!!!!102,|4|134;|'
 1940  >|>34|?!!!!1802|?!!!!1836,|4|1612,|4|1204,|4|168;|'
 1945  >|>34|?!!!!68|?!!!!102,|4|134;|'>|>34|?!!!!34|?
 1954  !!!!0.|'>{A9}{H9L11M29}|π|1|9|≡6|≡.|4|9The probability 
 1958  that both |εu |πand |εv |πare even is |f1|d34|); 
 1967  the probability that both are multiples of four 
 1975  is |f1|d316|); etc. Thus |εA |πhas the distribution 
 1983  given by the generating function|'{A9}|f3|d34|)|4α+↓|4|f3|d3
 1988  16|)|εz|4α+↓|4|f3|d364|)z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4|
 1988  (|f3|d34|)|d21|4α_↓|4z/4|)|4.|;{A9}|πThe mean 
 1991  is |f1|d33|), and the standard deviation is |¬H|v4|f2|d39|)|
 1998  4α+↓|4|f1|d33|)|4α_↓|4|f1|d39|)|4α=↓|4|f2|d33|). 
 1999  If |εu, v |πare independently and uniformly distributed 
 2007  with |ε1|4|¬E|4u,|4v|4|¬W|42|gN, |πthen some 
 2011  small correction terms are needed; the mean is 
 2019  then actually|'{A9}|ε(2|gN|4α_↓|41)|gα_↓|g2|4|↔k|uc|)1|¬Ek|¬
 2021  EN(2|gN|gα_↓|gk|4α_↓|41)|g2|4α=↓|4|f1|d33|)|4α_↓|4|f4|d33|)(
 2021  2|gN|4α_↓|41)|gα_↓|g1|4α+↓|4N(2|gN|4α_↓|41)|gα_↓|g2.|;
 2022  {A9}|π|9|1|≡7|≡.|4|9When |εu, v |πare not both 
 2028  even, each of the cases (even, odd), (odd, even), 
 2037  (odd, odd) is equally probable, and |εB|4α=↓|41, 
 2044  0, 0 |πin these cases. Hence |εB|4α=↓|4|f1|d33|) 
 2051  |πon the average. Actually, as in exercise 6, 
 2059  a small correction could be given to be strictly 
 2068  accurate when |ε1|4|¬E|4u,|4v|4|¬W|42|gN; |πthe 
 2072  probability that |εB|4α=↓|41 |πis actually|'{A9}|ε(2|gN|4α_↓
 2077  |41)|gα_↓|g2|↔k|uc|)1|¬Ek|¬EN|)(2|gN|gα_↓|gk|4α_↓|41)2|gN|gα
 2077  _↓|gk|4α=↓|4|f1|d33|)|4α_↓|4|f1|d33|)(2|gN|4α_↓|41)|gα_↓|g1.
 2077  |;{A9}|π|9|1|≡8|≡.|4|9|εE |πis the number of 
 2083  subtraction cycles in which |εu|4|¬Q|4v, |πplus 
 2089  one if |εu |πis odd after step B1. If we change 
 2100  the inputs from |ε(u,|4v) |πto |ε(v,|4u), |πthe 
 2107  value of |εC |πstays unchanged, while |εE |πbecomes 
 2115  |εC|4α_↓|4E |πor |εC|4α_↓|4E|4α_↓|41; |πthe latter 
 2120  case occurs i= |εu |πand |εv |πare both odd after 
 2130  step B1, and this has probability |f1|d33|)|4α+↓|4|f2|d33|)/
 2136  (2|ε|gN|4α_↓|41). |πHence|'{A9}|εE|π|βa|βv|βe|4α=↓|4|εC|π|βa
 2138  |βv|βe|4α_↓|4|εE|π|βa|βv|βe|4α_↓|4|f1|d33|)|4α_↓|4|f2|d33|)/
 2138  (2|ε|gN|4α_↓|41).|;{A9}|π|1|9|≡9|≡.|4|9The binary 
 2141  algorithm _rst gets to B6 with |εu|4α=↓|41963, 
 2148  v|4α=↓|41359; |πthen |εt|4|¬L|4604, 302, 151, 
 2153  |πetc. The gcd is 302. Using Alforithm X we _nd 
 2163  that 2|4|¬O|431408|4α_↓|423|4|¬O|42718|4α=↓|4302.|'
 2165  {A3}|≡1|≡0|≡.|4|9(a) Two integers are relatively 
 2170  prime i= they are not both divisible by any prime 
 2180  number. (b) Rearrangement of the sum in (a), 
 2188  in terms of the denominators |εk|4α=↓|4p|β1|4.|4.|4.|4p|βr. 
 2194  (|πNote that each of the sums in (a), (b) is 
 2204  actually _nite.{H11}){H9} (c) |ε(n/k)|g2|4α_↓|4|"ln/k|"L|g2|
 2207  4α=↓|4O(n/k), |πso |εq|βn|4α_↓|4|¬K|ur|)1|¬Ek|¬En|)|4|≤m(k)(
 2209  n/k)|g2|4α=↓|4|¬K|ur|)1|¬Ek|¬En|)|4O(n/k)|4α=↓|4O(nH|βn). 
 2210  (|πd) |¬K|ur|)|εd|¬Dn|)|4|≤m(d)|4α=↓|4|≤d|β1|βn. 
 2212  |π[In fact we have the more general result|'{A9}|ε|↔k|uc|)d|
 2220  ¬Dn|)|4|≤m(d)|↔a|(n|d2d|)|↔s|gs|4α=↓|4n|gs|4α_↓|4|↔k|4|↔a|(n
 2220  |d2p|)|↔s|gs|4α+↓|1|1|¬O|4|¬O|4|¬O|4,|;{A9}|πas 
 2222  in part (b), where the sums are over the prime 
 2232  divisors of |εn, |πand this equals |εn|gs(1|4α_↓|41/p|urs|)1
 2238  |))|4.|4.|4.|4(1|4α_↓|41/p|urs|)r|)) |πif |εn|4α=↓|4p|ure|β1
 2240  |)1|)|4.|4.|4.|4p|ure|βr|)r|).]|'!!|1|1Notes|*/: 
 2242  |\|πThis proof of Theorem D is due to F. Mertens. 
 2252  |εJ. f|=4ur die reine und angew. Math. |≡7|≡7 
 2260  (1874), 289<291. |πThe technique gives a much 
 2267  stronger result, namely that |ε6|≤p|gα_↓|g2n|g2|4α+↓|4O(n|4|
 2271  πlog|4|εn) |πpairs of integers |εu|¬A{H11}({H9}f(n), 
 2276  f(n)|4α+↓|4n{H11}){H9}, v|4|¬A|4{H11}[{H9}g(n), 
 2278  g(n)|4α+↓|4n{H11}) {H9}|πare relatively prime, 
 2282  for arbitrary |εf |πand |εg. |πSimilarly, a set 
 2290  of |εk |πintegers is relatively prime with probability 
 2298  |ε1/(|¬K|ur|)n|¬R1|)|41/n|gk).|'{A3}|π|≡1|≡1|≡.|4|9(a) 
 2300  6/|ε|≤p|g2 |πtimes 1|4α+↓|4|f1|d34|)|4α+↓|4|f1|d39|), 
 2303  namely 49/6|ε|≤p|g2|4|¬V|4.82746. |π(b) 6/|ε|≤p|g2 
 2307  |πtimes 1/1|4α+↓|42/4|4α+↓|43/9|4α+↓|1|1|¬O|4|¬O|4|¬O|4, 
 2309  namely |¬X*3 {H11}({H9}This is true in spite of 
 2317  the result of exercise 12, and in spite of the 
 2327  fact that the average value of ln gcd(|εu,|4v) 
 2335  |πis a small, _nite number.{H11})|'{A3}{H9L11M29}|≡1|≡2|≡.|4
 2340  |9Let |ε|≤s(n) |πbe the number of positive divisors 
 2348  of |εn. |πThe answer is|'{A9}|ε|↔k|uc|)k|¬R1|)|4|≤s(k)|4|¬O|
 2353  4|(6|d2|≤p|g2k|g2|)|4α=↓|4|(6|d2|≤p|g2|)|4{H12}|↔a{H9}|↔k|uc
 2353  |)k|¬R1|)|4|(1|d2k|g2|){H12}|↔s{H9}|g2|4α=↓|4|(|≤p|g2|d26|)|
 2353  4.|;{A9}|π[Thus, the average is |εless |πthan 
 2360  2, although there are always at least two common 
 2369  divisors when |εu, v |πare not relatively prime.]|'
 2377  {A3}|≡1|≡3|≡.|4|91|4α+↓|4|f1|d39|)|4α+↓|4|f1|d325|)|4α+↓|1|1
 2377  |¬O|4|¬O|4|¬O|1|1α=↓|41|4α+↓|4|f1|d34|)|4α+↓|4|f1|d39|)|4α+↓
 2377  |1|1|¬O|4|¬O|4|¬O|1|1α_↓|4|f1|d34|)(1|4α+↓|4|f1|d34|)|4α+↓|4
 2377  |f1|d39|)|4α+↓|1|1|¬O|4|≡O|4|≡O).|'{A3}|≡1|≡4|≡.|4|9|εv|β1|4
 2378  α=↓|4|→|"cv/u|β3,|4v|β2|4α=↓M7O0|"cu/u|β3 |π(the 
 2380  sign depends on whether the number of iterations 
 2388  is even or odd). This follows from the fact that 
 2398  |εv|β1 |πand |εv|β2 |πare relatively prime to 
 2405  each other (throughout the algorithm), and that 
 2412  |εv|β1u|4α=↓|4|→α_↓v|β2v. |π[Hence |εv|β1u|4α=↓|4|πlcm(|εu,|
 2414  4v) |πat the close of the alforithm, but this 
 2423  is not an especially e∃cient way to compute the 
 2432  least common multiple. For a generalization, 
 2438  see exercise 4.6.1<18.]|'!!|1|1G. E. Collins 
 2444  has observed that |ε|¬Gu|¬G|4|¬E|4|f1|d32|)v/u|β3, 
 2448  |¬Gu|β2|¬G|4|¬E|4|f1|d32|)u/u|β3, |πat the termination 
 2452  of Algorithm X, except in certain trivial cases, 
 2460  since the _nal value of |εq |πis usually |→|¬R2. 
 2469  This bounds the size of |ε|¬Gu|β1|¬G, |¬Gu|β2|¬G 
 2476  |πthroughout the execution of the alforithm.|'
 2482  {A3}|≡1|≡5|≡.|4|9Apply Algorithm X to |εv |πand 
 2488  |εm, |πthus obtaining a value |εx |πsuch that 
 2496  |εxv|4|"o|41 |π(modulo |εm). |π(This can be done 
 2503  by simplifying Algorithm X so that |εu|β2 |πand 
 2511  |εv|β2 |πare not computed, since they are never 
 2519  used in the answer.) Then set |εw|4|¬L|4ux |πmod 
 2527  |εm. |π[It follows, as in exercise 30, that this 
 2536  process requires |εO(n|g2) |πunits of time, when 
 2543  it is applied to large |εn-|πbit numbers.]|'|H*?*?{U0}{H9L11M2
folio 772 galley 5
 2550  9}58320#Computer Programming!(Knuth/A.-W.)!F. 
 2552  772!ch. 4!g. 5c|'{A12}|π|≡1|≡6|≡.|4|9(a) Set 
 2557  |εt|β1|4α=↓|4x|4α+↓|42y|4α+↓|43z; |πthen |ε3t|β1|4α+↓|4y|4α+
 2559  ↓|42z|4α=↓|41, 5t|β1|4α_↓|43y|4α_↓|420z|4α=↓|43. 
 2561  |πEliminate |εy, |πthen |ε14t|β1|4α_↓|414z|4α=↓|46: 
 2565  |πNo solution. (b) This time |ε14t|β1|4α_↓|414z|4α=↓|40. 
 2571  |πDivide by 14, eliminate |εt|β1; |πthe general 
 2578  solution is |εx|4α=↓|48z|4α_↓|42, y|4α=↓|41|4α_↓|45z, 
 2582  z |πarbitrary.|'{A3}|≡1|≡7|≡.|9|4Let |εu|β1, 
 2586  u|β2, u|β3, v|β1, v|β2, v|β3 |πbe multiprecision 
 2593  variables, not just |εu |πand |εv. |πThe extended 
 2601  algorithm will act the same on |εu|β3 |πand |εv|β3 
 2610  |πas Algorithm L does on |εu |πand |εv. |πNew 
 2619  multiprecision operations are to set |εt|4|¬L 
 2625  Au|βj, t|4|¬L|4t|4α+↓|4Bv|βj, w|4|¬L|4Cu|βj, 
 2628  w|4|¬L|4w|4α+↓|4Dv|βj, u|βj|4|¬L|4t, v|βj|4|¬L|4w 
 2631  |πfor all |εj, |πin step L4; also if |εB|4α=↓|40 
 2640  |πin that step to set |εt|4|¬L|4u|βj|4α_↓|4qv|βj, 
 2646  u|βj|4|¬L|4v|βj, v|βj|4|¬L|4t |πfor all |εj |πand 
 2652  for |εq|4α=↓|4|"lu|β3/v|β3|"L. |πA similar modi_cation 
 2657  is made to step L1 if |εv|β3 |πis small. The 
 2667  inner loop (steps L2 and L3) is unchanged.|'{A3}|≡1|≡8|≡.|4|
 2675  9If |εmn|4α=↓|40, |πthe probabilities of the 
 2681  lattice-point model in the test are exact, so 
 2689  we may assume that |εm|4|¬R|4n|4|¬Q|40. |εValida 
 2695  vi, |πthe following values have been obtained:|'
 2702  {A3}!!|1|1|εCase |*/|↔O|\, m|4α=↓|4n. |πFrom (|εn,|4n) 
 2707  |πwe go to |ε(n|4α_↓|4t,|4n) |πwith probability 
 2713  |εt/2|gt|4α_↓|45/2|gt|gα+↓|g1|4α+↓|43/2|g2|gt, 
 2714  |πfor |ε2|4|¬E|4t|4|¬W|4n. (|πThese values are 
 2719  |f1|d316|), |f7|d364|), |f27|d3256|),|4.|4.|4.|4.) 
 2722  |πTo (0,|4|εn) |πthe probability is |εn/2|gn|gα_↓|g1|4α_↓|41
 2727  /2|gn|4α+↓|41/2|g2|gn|gα_↓|g2. |πTo (|εn,|4k) 
 2730  |πthe probability is the same as to |ε(k,|4n). 
 2738  |πThe algorithm terminates with probability |ε1/2|gn|gα_↓|g1
 2743  .|'{A3}!!|1|1Case |*/|↔P|\, m|4α=↓|4n|4α+↓|41. 
 2747  |πFrom (|εn|4α+↓|41, n) |πwe get to |ε(n,|4n) 
 2754  |πwith probability |f1|d38|) when |εn|4|¬Q|41, 
 2759  |πor 0 when |εn|4α=↓|41; |πto |ε(n|4α_↓|4t, n) 
 2766  |πwith probability 11/2|ε|gt|gα+↓|g3|4α_↓|43/2|g2|gt|gα+↓|g1
 2768  , |πfor |ε1|4|¬E|4t|4|¬W|4n|4α_↓|41. (|πThese 
 2772  values are |f5|d316|), |f1|d34|),|4.|4.|4.|4.) 
 2776  We get to (1,|4|εn) |πwith probability |ε5/2|gn|gα+↓|g1|4α_↓
 2782  |43/2|g2|gn|gα_↓|g1, |πfor |εn|4|¬Q|41; |πto 
 2786  (0,|4|εn) |πwith probability 3/2|gn|4α_↓|41/2|g2|g|εn|4α_↓|4
 2789  1/2|g2|gn|gα_↓|g1.|'!!|1|1Case |*/|↔L|\, m|4|¬R|4n|4α+↓|42. 
 2793  |πThe probabilities are given by the following 
 2800  table:|'{A6}|h|ε|∂(m|4α_↓|4n|4α_↓|41,|4n):|9|∂1/2|gt|4α+↓|43
 2801  /2|gm|gα_↓|gn|gα+↓|gt|gα+↓|g1,|91|4|¬W|4t|4|¬W|4n;|E|n|;
 2802  |L(m|4α_↓|41,|4n):|L1/2|4α_↓|43/2|gm|gα_↓|gn|gα+↓|g2|4α_↓|4|
 2802  ≤d|βn|β1/2|gm|gα+↓|g1;>|L(m|4α_↓|4t,|4n):|L1/2|gt|4α+↓|43/2|
 2803  gm|gα_↓|gn|gα+↓|gt|gα+↓|g1,|91|4|¬W|4t|4|¬W|4n;>
 2804  |L(m|4α_↓|4n,|4n):|L1/2|gn|4α+↓|41/2|gm,|9n|4|¬Q|41;>
 2805  |L(m|4α_↓|4n|4α_↓|41,|4n):|L1/2|gn|gα+↓|g1|4α+↓|41/2|gm|gα_↓
 2805  |g1;>|L(m|4α_↓|4n|4α_↓|4t,|4n):|L1/2|gn|gα+↓|gt,|91|4|¬W|4t|
 2806  4|¬W|4m|4α_↓|4n;>|L(0,|4n):|L1/2|gm|gα_↓|g1.>
 2808  {A6}!!|1|1[Note|*/: |\|πAlthough these exact probabilities 
 2813  will certainly improve on the lattice-point model 
 2820  considered in the text, they lead to recurrence 
 2828  relations of much greater complexity; and they 
 2835  will not provide the true behavior of Algorithm 
 2843  B, since for example the probability that gcd(|εu,|4v)|4α=↓|
 2850  45 |πis di=erent from the probability that gcd(|εu,|4v)|4α=↓
 2857  |47.]|'{A3}|h|εA|βn|βα+↓|β1|4|∂α=↓|4a|4α+↓|4|↔k|42|gα_↓|gkA|
 2858  βn|β(|βn|βα_↓|βk|β)|4α+↓|42|4(1|4α_↓|42|gα_↓|gn)|4α+↓|42|gα_
 2858  ↓|gnb|E|n|;|≡1|≡9|≡.|E|'| A|βn|βα+↓|β1|4|Lα=↓|4a|4α+↓|4|↔k|u
 2860  c|)1|¬Ek|¬En|)|42|gα_↓|gkA|ur|)(nα+↓1)(nα_↓k)|)|4α+↓|42|gα_↓
 2860  |gnb>{A4}|Lα=↓|4a|4α+↓|4|↔k|uc|)1|¬Ek|¬En|)|42|gα_↓|gkA|ur|)
 2861  n(nα_↓k)|)|4α+↓|4|(c|d22|)|4(1|4α_↓|42|gα_↓|gn)|4α+↓|42|gα_↓
 2861  |gnb>{A4}|Lα=↓|4a|4α+↓|4|f1|d32|)A|ur|)n(nα_↓1)|)|4α+↓|4|f1|
 2862  d32|)(A|βn|4α_↓|4a)|4α+↓|4|(c|d22|)|4(1|4α_↓|42|gα_↓|gn);>
 2863  {A6}|πnow substitute for |εA|βn|β(|βn|βα_↓|β1|β) 
 2867  |πfrom (36).|'{A3}|≡2|≡0|≡.|4|9The paths described 
 2872  in the hint have the same probability, only the 
 2881  subsequent termination of the alforithm has a 
 2888  di=erent probability; thus |ε|≤l|4α=↓|4k|4α+↓|41 
 2892  |πwith probability 2|gα_↓|ε|gk |πtimes the probability 
 2898  that |ε|≤l|4α=↓|41. |πLet the latter probability 
 2904  be |εp. |πWe know from the text that |ε|≤l|4α=↓|40 
 2913  |πwith approximate probability |f3|d35|); hence 
 2918  |f2|d35|)|4α=↓|4|εp(1|4α+↓|4|f1|d32|)|4α+↓|4|f1|d34|)|4α+↓|4
 2918  |f1|d38|)|4α+↓|1|1|¬O|4|¬O|4|¬O)|4α=↓|42p. |πThe 
 2920  average is |εp(1|4α+↓|4|f2|d32|)|4α+↓|4|f3|d34|)|4α+↓|4|f4|d
 2922  38|)|4α+↓|1|1|¬O|4|¬O|4|¬O)|4α=↓|4p(1|4α+↓|4|f1|d32|)|4α+↓|4
 2922  |f1|d34|)|4α+↓|4|f1|d38|)|4α+↓|1|1|¬O|4|¬O|4|¬O)|g2|4α=↓|44p
 2922  . |π[The exact probability that |ε|≤l|4α=↓|41 
 2928  |πis |f1|d35|)|4α_↓|4|f6|d35|)(|→α_↓|f1|d34|))|ε|gn 
 2930  |πif |εm|4|¬Q|4n|4|¬R|41, |f1|d35|)|4α_↓|4|f16|d35|)(|→α_↓|f
 2932  1|d34|))|gn |πif |εm|4α=↓|4n|4|¬R|42.]|'{A3}|π|≡2|≡1|≡.|4Sho
 2935  w that for _xed |εv |πand for |ε2|gm|4|¬W|4u|4|¬W|42|gm|gα+↓
 2942  |g1, |πwhen |εm |πis large, each subtraction-shift 
 2949  cycle of the algorithm reduces |"llg|β2|4|εu|"L 
 2955  |πby two on the average.|'{A3}|≡2|≡2|≡.|4|9Exactly 
 2961  |ε(N|4α_↓|4m)2|gm|gα_↓|g1|gα+↓|g|≤d|rm|r0 |πintegers 
 2963  |εu |πin the range |ε1|4|¬E|4u|42|gN |πhave |"llg|β2|4|εu|"L
 2969  |4α=↓|4m |πafter |εu |πhas been shifted right 
 2976  until it is odd.|'{A3}|≡2|≡3|≡.|4|9The _rst sum 
 2983  is |ε2|g2|gN|gα_↓|g2 |¬K|ur|)0|¬Em|¬Wn|¬WN|)|4mn2|gα_↓|gm|gα
 2985  _↓|gn{H11}({H9}(|≤a|4α+↓|4|≤b)N|4α+↓|4|≤g|4α_↓|4|≤am|4α_↓|4|
 2985  ≤bn{H11}){H9}. |πSince |ε|¬K|ur|)0|¬Em|¬Wn|)|4m2|gα_↓|gm|gα=
 2987  ↓|g2|4α_↓|4(nα+↓|41)2|g1|gα_↓|gn |πand |ε|¬K|ur|)0|¬Em|¬Wn|)
 2989   m(m|4α_↓|41)2|gα_↓|gm|4α=↓|44|4α_↓|4(n|g2|4α+↓|4n|4α+↓|42)2
 2990  |g1|gα_↓|gn, |πthe sum on |εm |πis |ε2|g2|gN|gα_↓|g2|4|¬K|ur
 2996  |)0|¬En|¬WN|)|4n2|gα_↓|gn{H11}({H9}(|≤g|4α_↓|4|≤a|4α+↓|4(|≤a
 2996  |4α+↓|4|≤b)N)(2|4α_↓|4(n|4α+↓|41)2|g1|gα_↓|gn|4α_↓|4|≤a(4|4α
 2996  _↓|4(n|g2|4α+↓|4n|4α+↓|42)2|g1|gα_↓|gn)|4α_↓|4|≤bn{H11}){H9}
 2996  |4α=↓|42|g2|gN|gα_↓|g2{H11}({H9}(|≤a|4α+↓|4|≤b)N|4|¬K|ur|)0|
 2996  ¬En|¬WN|)|4n2|gα_↓|gn(2|4α_↓|4(n|4α+↓|41)2|g1|gα_↓|gn)|4α+↓|
 2996  4O(1){H11}){H9}. |πThus the coe∃cient of |ε(|≤a|4α+↓|4|≤b)N 
 3002  |πin the answer is found to be 2|gα_↓|g2{H11}({H9}4|4α_↓|4(|
 3009  f4|d33|))|g3{H11}){H9}|4α=↓|4|f11|d327|). A similar 
 3012  argument applies to the other sum.|'!!|1|1[|εNote|*/: 
 3019  |\|πThe |εexact |πvalue of the sums  ay be obtained 
 3029  after some tedious calculation by means of the 
 3037  general formula|'{A6}|ε|↔k|uc|)0|¬Ek|¬Wn|)k|gmz|gk|4α=↓|4|(m
 3039  *3z|gm|d2(1|4α_↓|4z)|gm|gα+↓|g1|)|4α_↓|4|↔k|uc|)0|¬Ek|¬Em|)|4
 3039  |(m|gkn|gm|gα_↓|gkz|gn|gα+↓|gk|d2(1|4α_↓|4z)|gk|gα+↓|g1|)|;
 3040  {A6}|πwhich follows from summation by parts.]|'
 3046  |≡2|≡4|≡.|4|9Solving a recurrence similar to 
 3051  (34), we _nd that the number of times is |εA|βm|βn, 
 3061  |πwhere |εA|β0|β0|4α=↓|41, A|β0|βn|4α=↓|4(n|4α+↓|43)/2, 
 3064  A|βn|βn|4α=↓|4|f8|d35|)|4α_↓|4(3n|4α+↓|413)/(9|4|¬O|42|gn)|4
 3064  α+↓|4|f128|d345|)(|→α_↓|f1|d34|))|gn |πif |εn|4|¬R|41, 
 3067  A|βm|βn|4α=↓|4|f16|d315|)(|→α_↓|f1|d34|))|gn 
 3068  |πif |εm|4|¬Q|4n|4|¬R|41. |πSince the condition 
 3073  |εu|4α=↓|41 |πor |εv|4α=↓|41 |πis therefore satis_ed 
 3079  only about 1.6 times in an average run, it is 
 3089  not worth making the suggested test each time 
 3097  step B5 is performed. (Of course the lattice 
 3105  model is not completely accurate, but it seems 
 3113  reasonable to believe that it is not too inaccurate 
 3122  for this application.)|'{A3}|≡2|≡5|≡.|4|9(a) 
 3126  |εF|βn|βα+↓|β1(x)|4α=↓|4|¬K|ur|)d|¬R1|)2|gα_↓|gd|4|πPr(|εX|β
 3126  n|4|¬W|41 |πand |ε2|gd/(X|urα_↓1|)n|)|4α_↓|41)|4|¬W|4x 
 3129  |πor |εX|βn|4|¬Q|41 |πand (|εX|βn|4α_↓|41)/2|gd|4|¬W|4x{H11}
 3132  ){H9}|4α=↓|4|¬K|βd|β|¬R|β1|42|gα_↓|gd{H11}({H9}F|βn(1/(1|4α+
 3132  ↓|42|gdx|gα_↓|g1){H11}){H9}|4α+↓|4F|βn(1|4α+↓|42|gdx)|4α_↓|4
 3132  F|βn(1){H11}){H9}. |π(b) |εG|βn|βα+↓|β1(x)|4α=↓|41|4α_↓|4|¬K
 3134  |βd|β|¬R|β12|gα_↓|gd{H11}({H9}G|βn(1/(1|4α+↓|42|gdx))|4α_↓|4
 3134  G|βn(1/(1|4α+↓|42|gdx|gα_↓|g1)){H11}){H9}. (|πc) 
 3136  |εH|βn(x)|4α=↓|4|¬K|βd|β|¬R|β12|gα_↓|gd|4|πPr{H11}({H9}Y|βn|
 3136  4|¬E|4x and |ε(1|4α_↓|4Y|βn)/2|gd|4|¬E|4x{H11}){H9}|4α=↓|4|¬
 3138  K|βd|β|¬R|β1|42|gα_↓|gd|4|πmax{H11}({H9}0,|4|εG|βn(x)|4α_↓|4
 3138  G|βn(1|4α_↓|42|gdx){H11}){H9}.|'!!|1|1|πStarting 
 3140  with |εG|β0(x)|4α=↓|4x |πwe get rapid convergences 
 3146  to a limiting distribution where {H11}({H9}G(.1),|4.|4.|4.|4
 3151  ,|4|εG(.9){H11}){H9}|4α=↓|4(.2750, .4346, .5544, 
 3154  .6507, .7310, .7995, .8590, .9114, .9581). |πThe 
 3161  expected value of ln max(|εu|βn|m1v|βn)/|πmax(|εu|βn|βα+↓|β1
 3165  , v|βn|βα+↓|β1) |πis |¬J|ur1|)0|)|ε|4H|βn(t)|4dt/t, 
 3169  |πand Brent has shown that this can be written|'
 3178  {A6}{A6}|↔j|ur1|)1/3|)|4|(|εG|βn(t)|d2t|)|4dt|4α_↓|4|↔j|ur1/
 3178  3|)0|)|4|(G|βn(t)|d21|4α_↓|4t|)|4dt|4α+↓|4|↔k|uc|)k|¬R1|)|42
 3178  |gα_↓|gk|ur1/(1α+↓2|gk)|)1/(1α+↓2|gk|gα+↓|g1)|)|4|(G|βn(t)|d
 3178  2t(1|4α_↓|4t)|)|4dt.|;{A6}{H9L11M29}|π|≡2|≡6|≡.|4|9By 
 3180  induction, the length is |εm|4α+↓|4|"ln/2|"L 
 3185  |πwhen |εm|4|¬R|4n, |πexcept that when |εm|4α=↓|4n|4α=↓|41 
 3191  |πthere is |εno |πpath to (0,|40).|'|Hβ*?*?*?{U0}{H9L11M29}5832
folio 776 galley 6
 3197  0#Computer Programming!(Knuth/A.-W.)!ch. 4!f. 
 3200  776!g. 6c|'{A12}|≡2|≡7|≡.|4|9Let |εa|βn|4α=↓|4{H11}({H9}2|gn
 3203  |4α_↓|4(|→α_↓1)|gn{H11}){H9}/3; |πthen |εa|β0, 
 3206  a|β1, a|β2,|4.|4.|4.|4α=↓|40, 1, 1, 3, 5, 11, 
 3213  21,|4.|4.|4. (|πThis sequence of numbers has 
 3219  an interesting pattern of zeros and ones in its 
 3228  binary representation. Note that |εa|βn|4α=↓|4a|βn|βα_↓|β1|4
 3232  α+↓|42a|βn|βα_↓|β2, |πand |εa|βn|4α+↓|4a|βn|βα+↓|β1|4α=↓|42|
 3234  gn..) |πFor |εm|4|¬Q|4n, |πlet |εu|4α=↓|42|gm|gα+↓|g1|4α_↓|4
 3238  a|βn|βα+↓|β2, v|4α=↓|4a|βn|βα+↓|β2. |πFor |εm|4α=↓|4n|4|¬Q|4
 3241  0, |πlet |εu|4α=↓|4a|βn|βα+↓|β2, v|4α=↓|42a|βn|βα+↓|β1, 
 3245  |πor |εu|4α=↓|42a|βn|βα+↓|β1, v|4α=↓|4a|βn|βα+↓|β2 
 3248  (|πdepending on which is larger). Another example 
 3255  for |εm|4α=↓|4n|4|¬Q|40 |πis |εu|4α=↓|42|gn|gα+↓|g1|4α_↓|41,
 3258   v|4α=↓|42|gn|gα+↓|g1|4α_↓|42; |πthis takes more 
 3263  shifts, and gives |εC|4α=↓|4n|4α+↓|41, D|4α=↓|42n, 
 3268  E|4α=↓|41.|'{A3}|π|≡2|≡8|≡.|4|9This is a problem 
 3273  where it appears to be necessary to prove |εmore 
 3282  |πthan was asked just to prove what was asked. 
 3291  Let us prove the following: |εIf u, v are positive 
 3301  integers, Algorithm B takes |¬E1|4α+↓|4|"l|πlg|β2|4max(|εu,|
 3305  4v)|"L |εsubtraction cycles|*/; |\and if equality 
 3311  holds, then |"l|πlg|β2|4(|εu|4α+↓|4v)|"L|4|¬Q|4|"l|πlg|β2|4m
 3313  ax(|εu,|4v)|"L.|'|π!!|1|1For convenience, let 
 3317  us assume that |εu|4|¬R|4v; |πlet |εm|4α=↓|4|"l|πlg|β2|4|εu|
 3322  "L, n|4α=↓|4|"l|πlg|β2|4|εv|"L; |πand let us 
 3327  use the ``lattice-point'' terminology, saying 
 3332  that we are ``at point |ε(m,|4n).'' |πThe proof 
 3340  is by induction on |εm|4α+↓|4n.|'!!|1|1Case |*/|↔O|\, 
 3347  m|4α=↓|4n. |πClearly, |"llg|β2(|εu|4α+↓|4v)|"L|4|¬Q|4|"l|πlg
 3349  |β2|4|εu|"L |πin this case. If |εu|4α=↓|4v |πthe 
 3356  result is trivial; otherwise the next subtraction-shift 
 3363  cycle takes us to a point |ε(m|4α_↓|4k,|4m). 
 3370  |πBy induction, at most |εm|4α+↓|41 |πfurther 
 3376  subtraction steps will be required; but if |εm|4α+↓|41 
 3384  |πmore |εare |πneeded, we have |"llg|β2{H11}({H9}(|εu|4α_↓|4
 3389  v)2|gα_↓|gr|4α+↓|4v{H11}){H9}|"L|4|¬Q|4|"l|πlg|β2|4|εv|"L, 
 3390  |πwhere |εr|4|¬R|41 |πis the number of right 
 3397  shifts that were made. This is impossible, since 
 3405  |ε(u|4α_↓|4v)2|gα_↓|gr|4α+↓|4v|4|¬W|4(u|4α_↓|4v)|4α+↓|4v|4α=
 3405  ↓|4u, |πso at most |εm |πfurther steps are needed.|'
 3414  !!|1|1|εCase |*/|↔P|\, m|4|¬Q|4n. |πThe next subtraction 
 3420  step takes us to |ε(m|4α_↓|4k,|4n), |πand at 
 3427  most 1|4α+↓|4max(|εm|4α_↓|4k,|4n)|4|¬E|4m |πfurther 
 3430  steps will be required. Now if |εm |πfurther 
 3438  steps |εare |πrequired, then |εu |πhas been replaced 
 3446  by |εu|¬S|4α=↓|4(u|4α_↓|4v)2|gα_↓|gr |πfor some 
 3450  |εr|4|¬R|41. |πBy induction, |"llg|β2(|εu|¬S|4α+↓|4v)|"L|4|¬
 3453  R|4m; |πhence|'{A9}|"llg|β2(|εu|4α+↓|4v)|"L|4α=↓|4|"l|πlg|β2
 3455  |42{H11}({H9}(|εu|4α_↓|4v)/2|4α+↓|4v{H11}){H9}|"L|4|¬R|4|"l|
 3455  πlg|β2|42(|εu|¬S|4α+↓|4v)|"L|4|¬R|4m|4α+↓|41|4|¬Q|4|"l|πlg|β
 3455  2|4|εu|"L.|;{A9}|π|≡2|≡9|≡.|4|9Subtract the |εk|πth 
 3459  column from the |ε2k|πth, |ε3k|πth, |ε4k|πth, 
 3465  etc., for |εk|4α=↓|41, 2, 3,|4.|4.|4.|4. |πThe 
 3471  result is a triangular matrix with |εx|βk |πon 
 3479  the diagonal in column |εk, |πwhere |εm|4α=↓|4|¬K|ur|)d|¬Dm|
 3485  )|4x|βd. |πIt follows that |εx|βm|4α=↓|4|≤'(m), 
 3490  |πso the determinant is |ε|≤'(1)|≤'(2)|4.|4.|4.|4|≤'(n). 
 3495  [|πIn general, ``Smith's determinant,'' in which 
 3501  the |ε(i,|4j) |πelement is |εf|1{H11}({H9}|πgcd(|εi,|4j){H11
 3505  }){H9} |πfor an arbitrary function |εf, |πis 
 3512  equal to |≥7|ur|)|ε1|¬Em|¬En|)|4|¬K|ur|)d|¬Dm|)|4|≤m(m/d)f(d
 3514  ), |πby the same argument. See L. E. Dickson, 
 3523  |εHistory of the Theory of Numbers |≡1 |π(New 
 3531  York: Chelsea, 1952), 122<123.]|'{A3}|≡3|≡0|≡.|4|9To 
 3536  determine |εA |πand |εr |πsuch that |εu|4α=↓|4Av|4α+↓|4r, 
 3543  0|4|¬E|4r|4|¬W|4v, |πusing ordinary long division, 
 3548  takes |εO{H11}({H9}(1|4α+↓|4|πlog|4|εA)(|πlog|4|εu){H11}){H9
 3549  } |πunits of time. If the quotients during the 
 3558  algorithm are |εA|β1, A|β2,|4.|4.|4.|4, A|βm, 
 3563  |πthen |εA|β1A|β2|4.|4.|4.|4A|βm|4|¬E|4u, |πso 
 3566  log |εA|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4|πlog|4|εA|βm|4|¬E|
 3567  4|πlog|4|εu. |πAlso |εm|4α=↓|4O(|πlog|4|εu).|'
 3570  {A3}|π|≡3|≡1|≡.|4|9Since |ε(a|gu|4α_↓|41)|4|πmod|4(|εa|gv|4α
 3571  _↓|41)|4α=↓|4a|gu|4|π|gm|go|gd|4|ε|gv|4α_↓|41 
 3572  (|πcf. Eq. 4.3.2<19), we _nd that gcd(|εa|gm|4α_↓|41, 
 3579  a|gn|4α_↓|41)|4α=↓|4a|ur|πgcd(|εm,n)|)|)|4α_↓|41 
 3580  |πfor all positive integers |εa.|'{A3}{H9L11M29}|π|≡3|≡2|≡.|
 3585  4|9Yes, to |εO{H11}({H9}n(|πlog|4|εn)|g2(|πlog|4log|4|εn){H1
 3587  1}){H9}; |πsee A. Sch|=4onhage, |εActa Informatica 
 3593  |≡1 (1971), |π139<144. [But Algorithm L is better 
 3601  in practice unless |εn |πis extremely large.]|'
 3608  {A3}|≡3|≡4|≡.|4|9Keep track of the most signi_cant 
 3614  and least signi_cant words of the operands (the 
 3622  most signi_cant is used to guess the sign of 
 3631  |εt |πand the least signi_cant is to determine 
 3639  the amount of right shift), while building a 
 3647  2|4α⊗↓|42 matrix of single-precision integers 
 3652  |εA |πsuch that |εA(|fu|d5v|))|4α=↓|4(|fu|¬Sw|d5v|¬Sw|)) 
 3656  |πwhere |εu|¬S |πand |εv|¬S |πare smaller than 
 3663  |εu |πand |εv. (|πInstead of dividing the simulated 
 3671  odd operand by 2, multiply the other one by 2, 
 3681  until obtaining multiples of the word size |εw 
 3689  |πafter exactly lg |εw |πshifts.) Experiments 
 3695  show this algorithm running four times as fast 
 3703  as Algorithm L.|'{A3}{A24}{H10L12M29}|∨S|∨E|∨C|∨T|∨I|∨O|∨N 
 3707  |∨4|∨.|∨5|∨.|∨3|'{A12}{H9L11M29}|1|9|≡1|≡.|4|9The 
 3709  running time is about 19.02|εT|4α+↓|46, |πjust 
 3715  a tri⊗e slower than Program 4.5.2A.|'{A3}|1|9|≡2|≡.|9|4|↔a|(
 3721  |εQ|βn(x|β1,|4.|4.|4.|4,|4x|βn)|d2Q|βn|βα_↓|β1(x|β2,|4.|4.|4
 3721  .|4,|4x|βn)|)!|(Q|βn|βα_↓|β1(x|β1,|4.|4.|4.|4,|4x|βn|βα_↓|β1
 3721  )|d5Q|βn|βα_↓|β2(x|β2,|4.|4.|4.|4,|4x|βn|βα_↓|β1)|)|↔s.|'
 3722  {A3}|1|9|≡3|≡.|4|9Q|βn(x|β1,|4.|4.|4.|4,|4x|βn).|'
 3723  {A3}|1|9|≡4|≡.|4|9|πBy induction, or by taking 
 3728  the determinant of the matrix product in exercise 
 3736  2.|'{A3}|1|9|≡5|≡.|4|9When the |εx'|πs are positive, 
 3742  the |εq'|πs of (9) are positive, and |εq|βn|βα+↓|β1|4|¬Q|4q|
 3749  βn|βα_↓|β1; |πhence (9) is an alternating series 
 3756  of decreasing terms, and it converges if and 
 3764  only if |εq|βn|4|¬M|4|¬X. |πBy induction, if 
 3770  the |εx'|πs are greater than |ε|≤e, q|βn|4|¬R|4c(1|4α+↓|4|≤e
 3776  /2)|gn, |πwhere |εc |πis chosen such that |ε1|4|¬R|4c, 
 3784  |≤e|4|¬R|4c(1|4α+↓|4|≤e/2). |πBut if |εx|βn|4α=↓|41/2|gn 
 3788  |πthen |εq|βn|4|¬E|42|4α_↓|41/2|gn.|'{A3}|1|9|≡6|≡.|4|9|πIt 
 3791  su∃ces to prove that |εA|β1|4α=↓|4B|β1; |πand 
 3797  from the fact that |ε0|4|¬E|4|"Cx|β1,|4.|4.|4.|4,|4x|βn|"C|4
 3801  |¬W|41 |πwhenever |εx|β1,|4.|4.|4.|4,|4x|βn |πare 
 3805  positive integers, we have |εB|β1|4α=↓|4|"l1/X|"L|4α=↓|4A|β1
 3809  .|'{A3}|π|1|9|≡7|≡.|4|9Only 1|42|4.|4.|4.|4|εn 
 3812  |πand |εn|4.|4.|4.|42|41. |π(The variable |εx|βk 
 3817  |πappears in exactly |εF|βkF|βn|βα_↓|βk |πterms; 
 3822  hence |εx|β1 |πand |εx|βn |πcan only be permuted 
 3830  into |εx|β1 |πand |εx|βn. |πIf |εx|β1 |πand |εx|βn 
 3838  |πare _xed by the permutation, it follows by 
 3846  induction that |εx|β2,|4.|4.|4.|4,|4x|βn|βα_↓|β1 
 3849  |πare also _xed.)|'{A3}|1|9|≡8|≡.|4|9This is 
 3854  equivalent to|'{A9}|ε|(Q|βn|βα_↓|β2(A|βn|βα_↓|β1,|4.|4.|4.|4
 3856  ,|4A|β2)|4α_↓|4XQ|βn|βα_↓|β1(A|βn|βα_↓|β1,|4.|4.|4.|4,|4A|β1
 3856  )|d2Q|βn|βα_↓|β1(A|βn,|4.|4.|4.|4,|4A|β2)|4α_↓|4XQ|βn(A|βn,|
 3856  4.|4.|4.|4,|4A|β1)|)|4α=↓|4α_↓|(1|d2X|βn|)|4,|;
 3857  |π{A9}and by (6) this is equivalent to|'{A9}*?*?|εX|4α=↓|4|(Q|
 3864  βn|βα_↓|β1(A|β2,|4.|4.|4.|4,|4A|βn)|4α+↓|4X|βnQ|βn|βα_↓|β2(A
 3864  |β2,|4.|4.|4.|4,|4A|βn|βα_↓|β1|d2Q|βn(A|β1,|4.|4.|4.|4,|4A|β
 3864  n)|4α+↓|4X|βnQ|βn|βα_↓|β1(A|β1,|4.|4.|4.|4,|4A|βn|βα_↓|β1)|)
 3864  |4.|;{A9}|π|1|9|≡9|≡.|4|9(a) By de_nition. (b), 
 3869  (d) Prove this when |εn|4α=↓|41, |πthen apply 
 3876  (a) to get the result for general |εn. |π(c) 
 3885  Prove when |εn|4α=↓|4k|4α+↓|41, |πthen apply 
 3890  (a).|'{A3}|≡1|≡0|≡.|4|9If |εA|β0|4|¬Q|40, |πthen 
 3894  |εB|β0|4α=↓|40, B|β1|4α=↓|4A|β0, B|β2|4α=↓|4A|β1, 
 3897  B|β3|4α=↓|4A|β2, B|β4|4α=↓|4A|β3, B|β5|4α=↓|4A|β4, 
 3900  m|4α=↓|45. |πIf |εA|β0|4α=↓|40, |πthen |εB|β0|4α=↓|4A|β1, 
 3905  B|β1|4α=↓|4A|β2, B|β2|4α=↓|4A|β3, B|β3|4α=↓|4A|β4, 
 3908  m|4α=↓|43. |πIf |εA|β0|4α=↓|4|→α_↓1 |πand |εA|β1|4α=↓|41, 
 3913  |πthen |εB|β0|4α=↓|4|→α_↓(A|β2|4α+↓|42), B|β1|4α=↓|41, 
 3916  B|β2|4α=↓|4A|β3|4α_↓|41, B|β3|4α=↓|4A|β4, m|4α=↓|43. 
 3919  |πIf |εA|β0|4α=↓|4|→α_↓1 |πand |εA|β1|4|≡Q|41, 
 3923  |πthen |εB|β0|4α=↓|4|→α_↓2, B|β2|4α=↓|4A|β1|4α_↓|42, 
 3926  B|β3|4α=↓|4A|β2, B|β4|4α=↓|4A|β3, B|β5|4α=↓|4A|β4, 
 3929  m|4α=↓|45. |πIf |εA|β0|4|¬W|4|→α_↓1, |πthen |εB|β0|4α=↓|4|→α
 3933  _↓1, B|β1|4α=↓|41, B|β2|4α=↓|4|→α_↓A|β0|4α_↓|42, 
 3936  B|β3|4α=↓|41, B|β4|4α=↓|4A|β1|4α_↓|41, B|β5|4α=↓|4A|β2, 
 3939  B|β6|4α=↓|4A|β3, B|β7|4α=↓|4A|β4. |π[Actually, 
 3942  the last three cases involve eight subcases; 
 3949  if any of the |εB'|πs is set to zero, the values 
 3960  should be ``collapsed together'' by using the 
 3967  rule of exercise 9(c). For example, if |εA|β0|4α=↓|4|→α_↓1, 
 3975  A|β1|4α=↓|4A|β3|4α=↓|41, |πwe actually have |εB|β0|4α=↓|4|→α
 3979  _↓(A|β2|4α+↓|42), B|β1|4α=↓|4A|β4|4α+↓|41, m|4α=↓|41. 
 3982  |πDouble collapsing occurs when |εA|β0|4α=↓|4|→α_↓2, 
 3987  A|β1|4α=↓|41.]|'|H*?*?*?*?58320#Computer Programming!(Knuth/A.-W
folio 777 galley 7 WARNING: Couldn't read the beginning of this galley.
 3989  .)!f. 777!ch. 4!g. 7c|'{A12}|π|≡1|≡1|≡.|4|9Let 
 3994  |εq|βn|4α=↓|4Q|βn(A|β1,|4.|4.|4.|4,|4A|βn), q|ur|↔0|)n|)|4α=
 3995  ↓|4Q|βn(B|β1,|4.|4.|4.|4,|4B|βn), p|βn|4α=↓|4Q|βn|βα+↓|β1(A|
 3996  β0,|4.|4.|4.|4,|4A|βn), p|ur|↔0|)n|)|4α=↓|4Q|βn|βα+↓|β1(B|β0
 3997  ,|4.|4.|4.|4,|4B|βn). |πWe have |εX|4α=↓|4(p|βm|4α+↓|4p|βm|β
 4000  α_↓|β1X|βm)/(q|βm|4α+↓|4q|βm|βα_↓|β1X|βm), Y|4α=↓|4(p|ur|↔0|
 4001  )n|)|4α+↓|4p|ur|↔0|)nα_↓1|)Y|βn)/(q|ur|↔0|)n|)|4α+↓|4q|ur|↔0
 4001  |)nα_↓1|)Y|βn); |πtherefore if |εX|βm|4α=↓|4Y|βn, 
 4005  |πthe stated relation between |εX |πand |εY |πholds 
 4013  by (8). conversely, if |εX|4α=↓|4(qY|4α+↓|4r)/(sY|4α+↓|4t), 
 4018  |¬Gqt|4α_↓|4rs|¬G|4α=↓|41, |πwe may assume that 
 4023  |εs|4|¬R|40, |πand we can show that the partial 
 4031  quotients of |εX |πand |εY |πeventually agree 
 4038  by induction on |εs. |πThe result is clear when 
 4047  |εs|4α=↓|40, |πby exercise 9(d). |πIf |εs|4|¬Q|40, 
 4053  |πlet |εq|4α=↓|4as|4α+↓|4s|¬S (0|4|¬E|4s|¬S|4|¬W|4s). 
 4056  |πThen |εX|4α=↓|4a|4α+↓|41/{H11}({H9}(sY|4α+↓|4t)/(s|¬SY|4α+
 4057  ↓|4r|4α_↓|4at){H11}){H9}; |πsince |εs(r|4α_↓|4at)|4α_↓|4ts|¬
 4059  S|4α=↓|4sr|4α_↓|4tq, |πand |εs|¬S|4|¬W|4s, |πwe 
 4063  know by induction and exercise 10 that the partial 
 4072  quotients of |εX |πand |εY |πeventually agree. 
 4079  [|εNote|*/: |\|πThe fact that |εm |πis always 
 4086  odd in exercise 10 shows, by a close inspection 
 4095  of this proof, that|πBut by (12), |εp|βn|βα_↓|β1/q|βn|βα_↓|β
 4101  1/q|βn|βα_↓|β1 |πand |εp|βn/q|βn |πare extremely 
 4106  close to |εX; |πsince |εX|4|=|↔6α=↓|4Y, Y|4α_↓|4p|βn/q|βn 
 4112  |πand |εY|4α_↓|4p|βn|βα_↓|β1/q|βn|βα_↓|β1 |πwill 
 4115  have the same sign as |εY|4α_↓|4X |πfor all large 
 4124  |εn. |πThis proves that |εY|βn|4|¬W|40 |πfor 
 4130  all large |εn; |πhence 0|4|¬W|4|εX|βn|4|¬W|4X|βn|4α_↓|4Y|βn|
 4134  4α=↓|42|¬H|v4D|)/V|βn; V|βn |πmust be positive. 
 4139  Also |εU|βn|4|¬W|4|¬H|v4D|), |πsince |εX|βn|4|¬Q|40. 
 4143  |πHence |εV|βn|4|¬W|42|¬H|v{A9}|(|→α_↓V|βn|βα+↓|β1|d2V|βn|)|
 4144  4α=↓|4X|βnY|βn|4α=↓|4|((q|βnX|4α_↓|4p|βn)(q|βnY|4α_↓|4p|βn)|
 4144  d2(q|βn|βα_↓|β1X|4α_↓|4p|βn|βα_↓|β1)(q|βn|βα_↓|β1Y|4α_↓|4p|β
 4144  n|βα_↓|β1)|)|4.|;{A9}|π[A companion identity 
 4148  is|'{A9}|εVp|βnp|βn|βα_↓|β1|4α+↓|4U(p|βnq|βn|βα_↓|β1|4α+↓|4p
 4149  |βn|βα_↓|β1q|βn)|4α+↓|4{H11}({H9}(U|g2|4α_↓|4D)/V{H11}){H9}q
 4149  |βnq|βn|βα_↓|β1|4α=↓|4(|→α_↓1)|gnU|βn.]|;{A9}|π!!|1|1(d)|9If
 4150   |εX|βn|4α=↓|4X|βm |πfor |εn|4|=|↔6α=↓|4|εm, 
 4154  |πthen |εX |πis an irrational number which satis_es 
 4162  the quadratic equation |ε(q|βnX|4α_↓|4p|βn)/(q|βn|βα_↓|β1X|4
 4165  α_↓|4p|βn|βα_↓|β1|4α=↓|4(q|βmX|4α_↓|4p|βm)/(q|βm|βα_↓|β1X|4α
 4165  _↓|4p|βm|βα_↓|β1).|'|π|≡1|≡4|≡.|4|9As in exercise 
 4169  9, we need only verify the stated identities 
 4177  when |εc |πis the last partial quotient, and 
 4185  this veri_cation is trivial. Now Hurwitz's rule 
 4192  gives |ε2/e|4α=↓|4|"C), 2, 1, 2, 0, 1, 1, 1, 
 4201  1, 1, 0, 2, 3, 2, 0, 1, 1, 3, 1, 1, 0, 2, 5,|4.|4.|4.|"C. 
 4216  |πTaking the receiprocal, collapsing out the 
 4222  zeros as in exercise 9, and taking note of the 
 4232  pattern that appears, we _nd that (cf. exercise 
 4240  16) |εe/2|4α=↓|41|4α+↓|4|"C2, 2m|4α+↓|41,|43,|41,|42m|4α+↓|4
 4242  1,|41,|43|"C, m|4|¬R|40. [Schriften der phys.-|=4okon. 
 4247  Gesellschaft zu K|=4onigsberg |≡3|≡2 (1891), 
 4252  59<62.]|'{A3}{U0}{H9L11M29}|≡1|≡5|≡.|4|9{H11}({H9}This 
 4254  procedure maintains four integers (|εA, B, C, 
 4261  D) |πwith the invariant meaning that ``our remaining 
 4269  job is to output the continued fraction for |ε(Ay|4α+↓|4B)/(
 4277  Cy|4α+↓|4D), |πwhere |εy |πis the input yet to 
 4285  come.``{H11}){H9} Initially set |εj|4|¬L|4k|4|¬L|40, 
 4289  (A, B, C, D)|4|¬L|4(a, b, c, d); |πthen input 
 4298  |εx|βj |πand set (|εA, B, C, D)|4|¬L|4(Ax|βj|4α+↓|4B, 
 4305  A, Cx|βj|4α+↓|4D, C), j|4|¬L|4j|4α+↓|41, |πone 
 4310  or more times until |εC|4α+↓|4D |πhas the same 
 4318  sign as |εC. {H11}({H9}|πWhen |εj|4|¬R|41 |πand 
 4324  the input has not terminated, we know that |ε1|4|¬W|4y|4|¬W|
 4332  4|¬X; |πand when |εC|4α+↓|4D |πhas the same sign 
 4340  as |εC |πwe know therefore that (|εAy|4α+↓|4B)/(Cy|4α+↓|4D) 
 4347  |πlies between |ε(A|4α+↓|4B)/(C|4α+↓|4D) |πand 
 4351  |εA/C.{H11}){H9} |πNow comes the general step: 
 4357  If no integer lies strictly between (|εA|4α+↓|4B)/(C|4α+↓|4D
 4363  ) |πand |εA/C, |πoutput |εX|βk|4|¬L|4|"lA/C|"L, 
 4368  |πand set |ε(A, B, C, D)|4|¬L|4(C, D, A|4α_↓|4X|βkC, 
 4376  B|4α_↓|4X|βkD), k|4|¬L|4k|4α+↓|41; |πotherwise 
 4379  input |εx|βj |πand set |ε(A, B, C, D)|4|¬L|4(Ax|βj|4α+↓|4B, 
 4387  A, Cx|βj|4α+↓|4D, C), j|4|¬L|4j|4α+↓|41. |πThe 
 4392  general step is repeated ad in_nitum. However, 
 4399  if at any time the |ε⊂nal |εx|βj |πis input, 
 4408  the algorithm immediately switches gears: It 
 4414  outputs the continued fraction for |ε(Ax|βj|4α+↓|4B)/(Cx|βj|
 4419  4α+↓|4D), |πusing Euclid's algorithm, and terminates.|'
 4425  !!|1|1The following tableau shows the working 
 4431  for the requested example, where the matrix |ε|↔a|(b!A|d5D!C
 4438  |)|↔s |πbegins at the upper left corner then 
 4446  shifts right one on input, down one on output.|'
 4455  {A12}|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|4|1|1|∂!!!|∂!!!|∂!!!|∂!!!|∂!!
 4455  !|∂!!!|∂|E|;|J#>|>|;|εx|βj|;|→α_↓1|;5|;1|;1|;
 4464  1|;2|;1|;2|;|¬X|;>{B2}|J#>|>!X|βk:|'|9|4|439|;
 4474  |9|4|497|;|9|4|458|;|4|4|9193|;|;|;|;|;|;|;>|>
 4485  !|>|→α_↓2|'|→α_↓25|;|→α_↓62|;|4|4|937|;|4|4|9123|;
 4491  >|>!|4|4|9|92|'|;|;|4|4|916|;|4|4|9|9|153|;>|>
 4500  !|4|4|93|'|;|;|4|4|9|9|15|;|9|4|4|9|117|;22|;
 4506  39|;>|>!|4|4|97|'|;|;|4|4|9|9|11|;|4|4|9|4|4|4|4|42|;
 4514  |9|13|;|9|15|;8|;>|>!|4|4|91|'|;|;|;|;|1|91|;
 4525  |1|94|;5|;14|;>|>!|4|4|91|'|;|;|;|;|;|9|11|;3|;
 4538  |9|17|;>|>!|4|4|91|'|;|;|;|;|;|;2|;|9|17|;9|;
 4551  25|;>|>!|413|'|;|;|;|;|;|;1|;|9|10|;1|;|9|12|;
 4565  >|>!|4|4|92|'|;|;|;|;|;|;|;|;|;|9|11|;>|>!|¬X|'
 4581  |;|;|;|;|;|;|;|;|;|1|90|;>{A12}{H9L11M25}|π!!|1|1M. 
 4593  Mend|=2es France has shown that the number of 
 4601  quotients output per quotient input is asymptotically 
 4608  bounded between 1/|εr |πand |εr, |πwhere |εr|4α=↓|42|"lK(|¬G
 4614  ad|4α_↓|4bc|¬G)/2|"L|4α+↓|41 |πand |εK |πis the 
 4619  function de_ned in exercise 38; this bound is 
 4627  best possible. |ε[Colloquia Math. Soc. J|=1anos 
 4633  Bolyai, |πDebrecen, 1974, to appear.]|'!!|1|1The 
 4639  above algorithm can be generalized to compute 
 4646  the continued traction for |ε(axy|4α+↓|4bx|4α+↓|4cy|4α+↓|4d)
 4650  /(Axy|4α+↓|4Bx|4α+↓|4Cy|4α+↓|4D) |πfrom those 
 4653  of |εx |πand |εy |π(in particular, to compute 
 4661  sums an{U0}{H9L11M29}58320#Computer Programming!(Knuth/A.-W.
folio 781 galley 8
 4663  )!f. 781!ch. 4!g. 8c|'{A12}|≡1|≡6|≡.|4|9It is 
 4669  not di∃cult to prove by induction that |εf|βn(z)|4α=↓|4z/(2n
 4676  |4α+↓|41)|4α+↓|4O(z|g3) |πis an odd function 
 4681  with a convergent power series in a neighborhood 
 4689  of the origin, and that it satis_es the given 
 4698  di=erential equation. Hence|'{A9}|εf|β0(z)|4α=↓|4|"Cz|gα_↓|g
 4701  1|4α+↓|4f|β1(z)|"C|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4|"Cz|gα_↓|g1,|4
 4701  3z|gα_↓|g1,|4.|4.|4.|4,|4(2n|4α+↓|41)z|gα_↓|g1|4α+↓|4f|βn|βα
 4701  +↓|β1(z)|"C.|;{A9}|πIt remains to prove that 
 4707  lim|ur|)|εn|¬M|¬X|)|"Cz|gα_↓|g1, 3z|gα_↓|g1,|4.|4.|4.|4,|4(2
 4708  n|4α+↓|41)z|gα_↓|g1|"C|4α=↓|4f|β0(z). |π[Actually 
 4710  Euler, age 24, obtained continued fraction expansions 
 4717  for the considerably more general di=erential 
 4723  equation |εf|ur|↔0|)n|)(z)|4α=↓|4az|gm|4α+↓|4bf|βn(z)z|gm|gα
 4724  _↓|g1|4α+↓|4cf|βn(z)|g2; |πbut he did not bother 
 4730  to prove convergence, since formal manipulation 
 4736  and intuition were good enough in the eighteenth 
 4744  century.]|'!!|1|1There are several ways to prove 
 4751  the desired limiting equation. First, letting 
 4757  |εf|βn(z)|4α=↓|4|¬K|βk|4a|βn|βkz|gk, |πwe can 
 4760  argue from the equation|'{A9}|ε!(2n|4α+↓|41)a|βn|β1|4α+↓|4(2
 4764  n|4α+↓|43)a|βn|β3z|g2|4α+↓|4(2n|4α+↓|45)a|βn|β5z|g4|4α+↓|1|1
 4764  |¬O|4|¬O|4|¬O|'{A4}α=↓|41|4α_↓|4(a|β1z|4α+↓|4a|β3z|g3|4α+↓|4
 4765  a|β5z|g5|4α+↓|1|1|¬O|4|¬O|4|¬O)|g2!|?{A9}|πthat 
 4767  (|→α_↓1)|ε|gka|βn|β(|β2|βk|βα+↓|β1|β) |πis a 
 4770  sum of terms of the form |εc|βk/(2n|4α+↓|41)|gk|gα+↓|g1(2n|4
 4776  α+↓|4b|βk|β1)|4.|4.|4.|4(2n|4α+↓|4b|βk|βk), |πwhere 
 4778  the |εc|βk |πand |εb|βk|βm |πare positive integers 
 4785  independent of |εn. |πFor example, |ε|→α_↓a|βn|β7|4α=↓|44/(2
 4790  n|4α+↓|41)|g4(2n|4α+↓|43)(2n|4α+↓|45)(2n|4α+↓|47)|4α+↓|41/(2
 4790  n|4α+↓|41)|g4(2n|4α+↓|43)|g2(2n|4α+↓|47). |πThus 
 4792  |ε|¬Ga|ur|)(nα+↓1)k|)|¬G|4|¬E|4|¬Ga|βn|βk|¬G, 
 4793  |πand |ε|¬G|1f|βn(z)|¬G|4|¬E|4|πtan |ε|¬Gz|¬G 
 4796  |πfor |ε|¬Gz|¬G|4|¬W|4|≤p/2. |πThis uniform bound 
 4801  on |εf|βn(z) |πmakes the convergence proof very 
 4808  simple. Careful study of this argument reveals 
 4815  that the power series for |εf|βn(z) |πactually 
 4822  converges for |ε|¬Gz|¬G|4|¬W|4|≤p|¬H|v42n|4α+↓|41|)/2; 
 4825  |πthis is interesting, since it shows that the 
 4833  singularities of |εf|βn(z) |πget farther and 
 4839  farther away from the origin as |εn |πgrows, 
 4847  so the continued fraction actually represents 
 4853  tanh |εz throughout |πthe complex plane.|'!!|1|1Another 
 4860  proof gives further information of a di=erent 
 4867  kind: If we let|'!!|1|1Another proof gives further 
 4875  information of a di=erent kind: If we let|'{A9}|εA|βn(z)|4α=
 4883  ↓|4n*3|4|↔k|uc|)0|¬Ek|¬En|)|4|↔a|(2n|4α_↓|4k|d5n|)|↔sz|gk|↔hk
 4883  *3|4α=↓|4|↔k|uc|)k|¬R0|)|4|((n|4α+↓|4k)*3z|gn|gα_↓|gk|d2k*3(n|4
 4883  α_↓|4k)*3|)|4,|;{A9}|πthen|'{A9}|εA|βn|βα+↓|β1(z)|4α=↓|4|↔k|u
 4885  c|)k|¬R0|)|4|((n|4α+↓|4k|4α_↓|41)*3{H11}({H9}(4n|4α+↓|42)k|4α
 4885  +↓|4(n|4α+↓|41|4α_↓|4k)(n|4α_↓|4k){H11})|d2{H9}k*3(n|4α+↓|41|
 4885  4α_↓|4k)*3|)|4z|gn|gα+↓|g1|gα_↓|gk|;{A4}**************α=↓|4(4n|4α+↓|
 4886  42)A|βn(z)|4α+↓|4z|g2A|βn|βα_↓|β1(z).|;{A9}|πIt 
 4888  follows, by induction, that|'{A9}|εQ|βn|↔a|(1|d2z|),|4|(3|d2
 4892  z|)|4,|4.|4.|4.|4,|4|(2n|4α_↓|41|d2z|)|↔s|4|∂α=↓|4|(A|βn(2z)
 4892  |4α+↓|4A|βn(|→α_↓2z)|d22|gn|gα+↓|g1z|gn|)|4,|;
 4893  {A4}| Q|βn|βα_↓|β1|↔a|(3|d2z|)|4,|4.|4.|4.|4,|4|(2n|4α_↓|41|
 4893  d2z|)|↔s|4|Lα=↓|4|(A|βn(2z)|4α_↓|4A|βn(|→α_↓2z)|d22|gn|gα+↓|
 4893  g1z|gn|)|4.>{A9}|πHence|'|ε|"Cz|gα_↓|g1,|43z|gα_↓|g1,|4.|4.|
 4895  4.|4,|4(2n|4α_↓|41)z|gα_↓|g1|"C|4α=↓|4|(A|βn(2z)|4α_↓|4A|βn(
 4895  |→α_↓2z)|d2A|βn(2z)|4α+↓|4A|βn(|→α_↓2z)|)|4,|;
 4896  {A9}|πand we want to show that this ratio approaches 
 4905  tanh |εz. |πBy Eqa. 1.2.9<11 and 1.2.6<26,|'{A9}|εe|gzA|βn(|
 4912  →α_↓z)|4α=↓|4n*3|4|↔k|uc|)m|¬R0|)|4z|gm{H12}|↔a{H9}|↔k|uc|)0|
 4912  ¬Ek|¬En|)|4|↔a|(m|d5k|)|↔s|↔a|(2n|4α_↓|4k|d5n|)|↔s(|→α_↓1)|g
 4912  k{H12}|↔s{H9}|4|↔k|uc|)m|¬R0|)|4|↔a|(2n|4α_↓|4m|d5n|)|↔sz|gm
 4912  |4|(n*3|d2m*3|)|4.|;{A9}|πHence|'{A9}|εe|gzA|βn(|→α_↓z)|4α_↓|4
 4914  A|βn(z)|4α=↓|4R|βn(z)|4α=↓|4(|→α_↓1)|gnx|g2|gn|gα+↓|g1|4|↔k|
 4914  uc|)k|¬R0|)|4|((n|4α+↓|4k)*3x|gk|d2(2n|4α+↓|4k|4α+↓|41)*3k*3|)|
 4914  4.|;{A9}|π{H9L11M29}We now have (|εe|g2|gz|4α_↓|41){H11}({H9
 4918  }A|βn(2z)|4α+↓|4A|βn(|→α_↓2z){H11}){H9}|4α_↓|4(e|g2|gz|4α+↓|
 4918  41){H11}({H9}A|βn(2z)|4α_↓|4A|βn(|→α_↓2z){H11}){H9}|4α=↓|42R
 4918  |βn(2z); |πhence|'{A9}{H9L11M29}|ε|"Cz|gα_↓|g1,|43z|gα_↓|g1,
 4920  |4.|4.|4.|4,|4(2n|4α_↓|41)z|gα_↓|g1|"C|4α=↓|4|(2R|βn(2z)|d2{
 4920  H11}({H9}A|βn(2z)|4α+↓|4A|βn(|→α_↓2z){H11}){H9}(e|g2|gz|4α+↓
 4920  |41)|)|4.|;{A9}{H9L11M29}|πThus we have an exact 
 4926  formula for the di=erence. When |ε|¬Gz|¬G|4|¬E|4|f1|d32|), 
 4932  e|g2|gz|4α+↓|41 |πis bounded away from zero, 
 4938  |ε|¬GR|βn(2z)|¬G|4|¬E|4en*3/(2n|4α+↓|41)*3, |πand|'
 4940  {A9}|ε|f1|d32|)|¬GA|βn(2z)|4α+↓|4A|βn(|→α_↓2z)|¬G|4|¬R|4n*3{H
 4940  12}|↔a{H9}|↔a|(2n|d5n|)|↔s|4α_↓|4|↔a|(2n|4α_↓|42|d5n|)|↔s|4α
 4940  _↓|4|↔a|(2n|4α_↓|44|d5n|)|↔s|4α_↓|1|1|¬O|4|¬O|4|¬O{H12}|↔s|;
 4941  {A4}|¬R|4|((2n)*3|d2n*3|)|4(1|4α_↓|4|f1|d34|)|4α_↓|4|f1|d316|)
 4941  |4α_↓|1|1|¬O|4|¬O|4|¬O)|4α=↓|4|(2|d23|)|4|((2n)*3|d2n*3|)|4.|;
 4942  {A9}{H9L11M29}|πThus convergence is very rapid, 
 4947  even for complex values of |εz.|'|π!!|1|1To go 
 4955  from this continued fraction to the continued 
 4962  fraction for |εe|gz, |πwe have tanh |εz|4α=↓|41|4α_↓|42/(e|g
 4968  2|gz|4α+↓|41); |πhence we get the continued fraction 
 4975  representation for |ε(e|g2|gz|4α+↓|41)/2 |πby 
 4979  simple manipulations. Hurwitz's rule gives the 
 4985  expansion of |εe|g2|gz|4α+↓|41, |πfrom which 
 4990  we may subtract unity. For |εn |πodd,|' {A9}|εe|gα_↓|g2|g/|g
 4998  n|4α=↓|4|"C1,|43mn|4α+↓|4|"ln/2|"L,|4(12m|4α+↓|46)n,|4(3m|4α
 4998  +↓|42)n|4α+↓|4|"ln/2|"L,|41|"C,!!m|4|¬R|40.|;
 4999  !!|1|1|πAnother derivation has been given by 
 5005  C. S. Davis, |εJ. London Math. Soc. |≡2|≡0 (1945), 
 5014  194<198.|'{A3}{H9L11M29}|π|≡1|≡7|≡.|4|9(b)|4|4|"C|εx|β1|4α_↓
 5015  |41, 1, x|β2|4α_↓|42, 1, x|β3|4α_↓|42, 1,|4.|4.|4.|4,|41, 
 5021  x|β2|βn|βα_↓|β1|4α_↓|42, 1, x|β2|βn|4α_↓|41|"C.|'
 5024  !!|1|1(c)|1|91|4α+↓|4|"C1, 1, 3, 1, 5, 1,|4.|4.|4.|"C.|'
 5030  {A3}|π|≡1|≡9|≡.|4|9The sum for |ε1|4|¬E|4k|4|¬E|4N 
 5034  |πis log|ε|βb {H11}({H9}2|4|¬O|43|4.|4.|4.|4(N|4α+↓|41){H11}
 5036  ){H9}|4α_↓|4|πlog|ε|βb (1|4|¬O|42|4.|4.|4.|4N)|4α_↓|4|πlog|ε
 5037  |βb {H11}({H9}(2|4α+↓|4x)(3|4α+↓|4x)|4.|4.|4.|4(N|4α+↓|41|4α
 5038  +↓|4x){H11}){H9}|4α+↓|4|πlog|ε|βb {H11}({H9}(1|4α+↓|4x)(2|4α
 5039  +↓|4x)|4.|4.|4.|4(N|4α+↓|4x){H11}){H9}|4α=↓|4|πlog|ε|βb 
 5040  {H11}({H9}(1|4α+↓|4x)(N|4α+↓|41)/(N|4α+↓|41|4α+↓|4x){H11}){H
 5040  9}.|'{A3}{H9L11M29}|π|≡2|≡0|≡.|9|4Let |εH|4α=↓|4SG, 
 5043  g(x)|4α=↓|4(1|4α+↓|4x)G|¬S(x), h(x)|4α=↓|4(1|4α+↓|4x)H|¬S(x)
 5044  . |πThen (35) implies that |εh(x|4α+↓|41)/(x|4α+↓|42)|4α_↓|4
 5049  h(x)/(x|4α+↓|41)|4α=↓|4|→α_↓(1|4α+↓|4x)|gα_↓|g2g(1/(1|4α+↓|4
 5049  ){H11}){H9}/{H11}({H9}1|4α+↓|41/(1|4α+↓|4x){H11}){H9}.|'
 5050  {A3}|π|≡2|≡1|≡.|9|4|ε|≤'(x)|4α=↓|4c/(cx|4α+↓|41)|g2|4α+↓|4(2
 5050  |4α_↓|4c)/{H11}({H9}(c|4α_↓|41)x|4α+↓|41{H11}){H9}|g2, 
 5051  U|≤'(x)|4α=↓|41/(x|4α+↓|4c)|g2. |πWhen |εc|4|¬E|41, 
 5054  |πthe minimum of |ε|≤'(x)/U|≤'(x) |πoccurs at 
 5060  |εx|4α=↓|40 |πand is |ε2c|g2|4|¬E|42. |πWhen 
 5065  |εc|4|¬R|4|≤f|4α=↓|4|f1|d32|)(|¬H|v45|)|4α+↓|41), 
 5066  |πthe minimum occurs at |εx|4α=↓|41 |πand is 
 5073  |→|¬E|ε|≤f|g2. |πWhen |εc|4|¬V|41.31266 |πthe 
 5077  values at |εx|4α=↓|40 |πand |εx|4α=↓|41 |πare 
 5083  nearly equal and the minimum is |→|¬Q3.2; the 
 5091  bounds (0.29)|ε|gn|≤'|4|¬E|4U|gn|≤'|4|¬E|4(0.31)|gn|≤' 
 5093  |πare obtained. Still bounds come from well-chosen 
 5100  linear combinations |εTg(x)|4α=↓|4|¬K|4a|βj/(x|4α+↓|4c|βj).|
 5102  '{A3}|π|≡2|≡3|≡.|4|9By the interpolation formula 
 5107  of exercise 4.64<15 with |εx|β0|4α=↓|40, x|β1|4α=↓|4x, 
 5113  x|β2|4α=↓|4x|4α+↓|4|≤e, |πletting |ε|≤e|4|¬M|40, 
 5116  |πwe have the general identity |εR|ur|↔0|)n|)(x)|4α=↓|4{H11}
 5121  ({H9}R|βn(x)|4α_↓|4R|βn(0){H11})}h9}/x|4α+↓|4|f1|d32|)xR|βn{
 5121  H11}({H9}|≤u(x){H11}){H9} |πfor some |ε|≤u(x) 
 5125  |πbetween 0 and |εx, |πwhenever |εR|βn |πis a 
 5133  function with continuous second derivative. Hence 
 5139  in this case |εR|ur|↔0|)n|)(x)|4α=↓|4O(2|gα_↓|gn).|'
 5143  {A3}|π|≡2|≡4|≡.|4|9|¬X. [A. Khinchin, in |εcompos. 
 5148  Math. |≡1 (1935), 361<382, |πproved that the 
 5155  sum |εA|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4A|βn 
 5157  |πof the _rst |εn |πpartial quotients of a real 
 5166  number |εX |πwill be asymptotically |εn|4|πlg|4|εn, 
 5172  |πfor almost all |εX.]|'|Hβ*?*?*?*?{U0}{H9L11M29}58320#Computer 
folio 784 galley 9
 5177  Programming!(Knuth/A.-W.)!f. 784!ch. 4!g. 9c|'
 5181  {A12}|π|≡2|≡5|≡.|4|9Any union of intervals can 
 5186  be written as a union of disjoint intervals, 
 5194  since |ε|↔w|βk|β|¬R|β1|4I|βk|4α=↓|4|↔w|βk|β|¬R|β1 
 5196  (I|βk|4α_↓|4|↔w|ur|)1|¬Ej|¬Wk|)|4I|βj), |πand 
 5198  this is a disjoint union in which |εI|βk|4α_↓|4|↔w|β1|β|¬E|β
 5205  j|β|¬W|βk|4I|βj |πcan be expressed as a _nite 
 5212  union of disjoint intervals. Therefore we may 
 5219  take |ε|λI|4α=↓|4|↔w|4I|βk, |πwhere |εI|βk |πis 
 5224  an interval of length |ε|≤e/2|gk |πcontaining 
 5230  the |εk|πth rational number in [0,|41], using 
 5237  some enumeration of the rationals. In this case 
 5245  |ε|≤m(|λI-|4|¬E|4|≤e, |πbut |¬F|ε|λI|4|↔w|4P|βn|¬F|4α=↓|4n 
 5248  |πfor all |εn.|'{A3}|π|≡2|≡6|≡.|4|9The continued 
 5253  fractions |"C|εA|β1,|4.|4.|4.|4,|4A|βt|"C |πwhich 
 5256  appear are precisely those for which |εA|β1|4|¬Q|41, 
 5263  A|βt|4|¬Q|41, |πand |εQ|βt(A|β1, A|β2,|4.|4.|4.|4,|4A|βt) 
 5267  |πis a divisor of |εn. |πTherefore (6) completes 
 5275  the proof. {H11}({H9}|εNote|*/:|\ |πIf |εm|β1/n|4α=↓|4|"CA|β1
 5279  ,|4.|4.|4.|4,|4A|βt|"C |πand |εm|β2/n|4α=↓|4|"CA|βt,|4.|4.|4
 5281  .|4,|4A|β1|"C, |πwhere |εm|β1 |πand |εm|β2 |πare 
 5287  relatively prime to |εn, |πthen |εm|β1m|β2|4|"o|4|→|¬N1 
 5293  (|πmodulo |εn); |πthis rule de_nes the correspondence. 
 5300  When |εA|β1|4α=↓|41 |πan analogous symmetry is 
 5306  valid, according to (38).{H11}){H9}|'{A3}{H9L11M29}|≡2|≡7|≡.
 5310  |4|9First prove the result for |εn|4α=↓|4p|ge, 
 5316  |πthen for |εn|4α=↓|4rs, |πwhere |εr |πand |εs 
 5323  |πare relatively prime. alternatively, use the 
 5329  formulas in the next exercise.|'{A3}{H9L11M29}|≡2|≡8|≡.|4|9(
 5334  a) The left-hand side is multiplicative (see 
 5341  exercise 1.2.4<31), and it is easily evaluated 
 5348  when |εn |πis a power of a prime. (c) From (a), 
 5359  we have |εM|=4obius inversion formula|*/: |\|πIf 
 5365  |εf|1(n)|4α=↓|4|¬K|ur|)d|¬Dn|)|4g(d), |πthen 
 5367  |εg(n)|4α=↓|4|¬K|ur|)d|¬Dn|)|4|≤m(n/d)f|1(d).|'
 5368  {A3}|π|≡2|≡9|≡.|4|9The sum is approximately (12|4ln|42/|ε|≤p
 5372  |g2)|4|πln|4|εN*3/N|4α_↓|4|¬K|ur|)d|¬R1|)|4|*/|≤!|\(d)/d|g2|4α
 5372  +↓|41.47; |πhere |ε|¬K|ur|)d|¬R1|)|4|*/|≤!|\(d)/d|g2 
 5375  |πconverges to the constant value |ε|→α_↓|≤z|¬S(2)/|≤z(2), 
 5381  |πwhile ln|4|εN*3|4α=↓|4N|4|πln|4|εN|4α_↓|4N|4α+↓|4O(|πlog|4|
 5382  εN) |πby Stirling's approximation.|'{A3}|≡3|≡0|≡.|4|9The 
 5387  modi_ed algorithm a=ects the calculation if and 
 5394  only if the following division step in the unmodi_ed 
 5403  algorithm would have the quotient 1, and in this 
 5412  case it avoids the following division step. The 
 5420  probability that a given division step is avoided 
 5428  is the probability that |εA|βk|4α=↓|41 |πand 
 5434  that this quotient is preceded by an even number 
 5443  of quotients equal to 1. By the symmetry condition, 
 5452  this is the probability that |εA|βk|4α=↓|41 |πand 
 5459  is |εfollowed |πby an even number of quotients 
 5467  equal to 1. The latter happens if and only if 
 5477  |εX|βk|βα_↓|β1|4|¬Q|4|≤f|4α_↓|41|4α=↓|40.618|4.|4.|4.|4, 
 5478  |πwhere |ε|≤f |πis the golden ratio: For |εA|βk|4α=↓|41, 
 5486  A|βk|βα+↓|β1|4|¬Q|4|πi= |f2|d33|)|4|¬E|4|εX|βk|βα_↓|β1|4|¬W|
 5487  41; A|βk|4α=↓|4A|βk|βα+↓|β1|4α=↓|4A|βk|βα+↓|β2|4α=↓|41, 
 5489  A|βk|βα+↓|β3|4|¬Q|41 |πi= |f5|d38|)|4|¬E|4|εX|βk|βα_↓|β1|4|¬
 5491  W|4|f2|d33|); |πetc. Thus we save approximately 
 5497  |εF|βk|βα_↓|β1(1)|4α_↓|4F|βk|βα_↓|β1(|≤f|4α_↓|41)|4|¬V|41|4α
 5497  _↓|4|πlg|β2|4|ε|≤f|4|¬V|40.306 |πof the division 
 5501  steps. The average number of steps is approximately 
 5509  (12|4ln|4|ε|≤f/|≤p|g2)|πln|4|εn, |πwhen |εv|4α=↓|4n 
 5512  |πand |εu |πis relatively prime to |εn. |πKronecker 
 5520  [|εVorlesungen |=4uber Zahlentheorie |≡1 |π(Leipzig: 
 5525  Teubner, 1901), 118] observed that this choice 
 5532  of least remainder in absolute value always gives 
 5540  the shortest possible number of iterations, over 
 5547  all algorithms which replace |εu |πby |ε(|→|¬Nu)|πmod 
 5554  |εv |πat each iteration. For further results 
 5561  see N. G. de Bruijn and W. M. Zaring, |εNieuw 
 5571  Archief voor Wiskunde (3) |≡1 (1953), 105<112.|'
 5578  |π!!|1|1On many computers, the modi_ed algorithm 
 5584  makes each division step longer; the idea of 
 5592  exercise 1, which saves |εall |πdivision steps 
 5599  when the quotient is unity, would be preferable 
 5607  in such cases.|'{A3}|≡3|≡1|≡.|4|9Let |εa|β0|4α=↓|40, 
 5612  a|β1|4α=↓|41, a|βn|βα+↓|β1|4α=↓|42a|βn|4α+↓|4a|βn|βα_↓|β1; 
 5614  |πthen |εa|βn|4α=↓|4{H11}({H9}(1|4α+↓|4|¬H|v42|))|gn|4α_↓|4(
 5615  1|4α_↓|4|¬H|v42|))|gn{H11}){H9}/2|¬H|v42|), |πand 
 5617  the worst case (in the sense of Theorem F) occurs 
 5627  when |εu|4α=↓|4a|βn|4α+↓|4a|βn|βα_↓|β1, v|4α=↓|4a|βn, 
 5630  n|4|¬R|42.|'|π!!|1|1This result is due to A. 
 5637  Dupr|=⊂e [|εJ. de Math. |≡1|≡1 (1846), 41<64], 
 5644  |πwho also investigated more general ``look-ahead'' 
 5650  procedures suggested by J. Binet. See P. Bachmann, 
 5658  |εNiedere Zahlentheorie |≡1 (|πLeipzig: Teubner, 
 5663  1902), 99<118, for a discussion of early analyses 
 5671  of Euclid's algorithm.|'{A3}|≡3|≡2|≡.|4|9|εQ|βm|βα_↓|β1(x|β1
 5674  ,|4.|4.|4.|4,|4x|βm|βα_↓|β1)Q|βn|βα_↓|β1(x|βm|βα+↓|β2,|4.|4.
 5674  |4.|4,|4x|βm|βα+↓|βn) |πcorresponds to Morse 
 5678  code sequence of length |ε(m|4α+↓|4n) |πin which 
 5685  a dash occupies positions |εm |πand |ε(m|4α+↓|41); 
 5692  |πthe other term corresponds to the opposite 
 5699  case. (Alternatively, use exercise 2. Actually 
 5705  Euler gave the more general identity |εQ|βm|βα+↓|βn(x|β1,|4.
 5711  |4.|4.|4,|4x|βm|βα+↓|βn)Q|βk(x|βm|βα+↓|β1,|4.|4.|4.|4,|4x|βm
 5711  |βα+↓|βk)|4α=↓|4Q|βm|βα+↓|βk(x|β1,|4.|4.|4.|4,|4x|βm|βα+↓|βk
 5711  )Q|βn(x|βm|βα+↓|β1,|4.|4.|4.|4,|4x|βm|βα+↓|βn)|4α+↓|4(|→α_↓1
 5711  )|gkQ|βm|βα_↓|β1(x|β1,|4.|4.|4.|4,|4x|βm|βα_↓|β1)Q|βn|βα_↓|β
 5711  k|βα_↓|β1(x|βm|βα+↓|βk|βα+↓|βz,|4.|4.|4.|4,|4x|βm|βα+↓|βn).{
 5711  H11}){H9}|'{A3}|π|≡3|≡3|≡.|4|9(a) The new representations 
 5716  are |εx|4α=↓|4m/d, y|4α=↓|4(n|4α_↓|4m)/d, x|¬S|4α=↓|4y|¬S|4α
 5719  =↓|4d|4α=↓|4|πgcd(|εm,|4n|4α_↓|4m), |πfor |f1|d32|)|εn|4|¬W|
 5721  4m|4|¬W|4n. |π(b) The relation |ε(n/x|¬S)|4α_↓|4y|4|¬E|4x|4|
 5725  ¬W|4n/x|¬S |πde_nes |εx. |π(c) Count the |εx|¬S 
 5732  |πsatisfying (b). (d) A pair of integers |εx|4|¬Q|4y|4|¬Q|40
 5739  , |πgcd(|εx,|4y|4α=↓|41), |πcan be uniquely written 
 5745  in the form |εx|4α=↓|4Q|βm(x|β1,|4.|4.|4.|4,|4x|βm), 
 5749  y|4α=↓|4Q|βm|βα_↓|β1(x|β1,|4.|4.|4.|4,|4x|βm|βα_↓|β1), 
 5750  |πwhere |εx|β1|4|¬R|42, m|4|¬R|41; |πhere |εy/x|4α=↓|4|"Cx|β
 5754  m,|4.|4.|4.|4,|4x|β1|"C. |π(e) It su∃ces to show 
 5760  that |ε|¬K|ur|)1|¬Ek|¬En/2|)T(k,|4n)|4α=↓|42|"ln/2|"L|4α+↓|4
 5761  h(n). |πFor |ε1|4|¬E|4k|4|¬E|4n/2 |πthe continued 
 5766  fractions |εk/n|4α=↓|4|"Cx|β1,|4.|4.|4.|4,|4x|βm)|¬Dn; 
 5768  |πand |εT(k,|4n)|4α=↓|42|4α+↓|4(m|4α_↓|41).|'
 5770  {A3}{H9L11M29}|π|≡3|≡4|≡.|4|9(a) Dividing |εx, 
 5773  y |πby gcd(|εx,|4y) |πyields |εg(n)|4α=↓|4|¬K|ur|)d|¬Dn|)|4h
 5777  (n/d); |πapply exercise 28(c), and use the symmetry 
 5785  between primed and unprimed variables. (b) For 
 5792  _xed |εy |πand |εt |πthe representations with 
 5799  |εxd|4|¬R|4x|¬S |πhave |εx|¬S|4|¬W|4|¬H|v4nd|); 
 5802  |πhence there are |εO(|¬H|v4nd|)/y) |πsuch representations. 
 5808  Now sum for |ε0|4|¬W|4t|4|¬E|4y|4|¬W|4|¬H|v4n/d|). 
 5812  |π(c) If |εs(y) |πis the given sum, then |ε|¬K|ur|)d|¬Dy|)|4
 5820  s(d)|4α=↓|4y(H|β2|βy|4α_↓|4H|βy)|4α=↓|4k(y), 
 5821  |πsay; hence |εs(y)|4α=↓|4|¬K|ur|)d|¬Dy|)|4k(y/d). 
 5824  |πNow |εk(y)|4α=↓|4y|4|πln|42|4α_↓|4|f1|d34|)|4α+↓|4|εO(1/y)
 5825  . |π(d) |ε|¬K|ur|)1|¬Ey|¬En|)|4|≤'(y)/y|g2|4α=↓|4|¬K|ur|)1|¬
 5827  Ey|¬En,d|¬Dy|)|4|≤m(d)/yd|4α=↓|4|¬K|ur|)cd|¬En|)|4|≤m(d)/cd|
 5827  g2. (|πsimilarly, |ε|¬K|ur|)1|¬Ey|¬En|)|4|≤s|βα_↓|β1(y)/y|g2
 5829  |4α=↓|4O(1).{H11}){H9} |π(e) |ε|¬K|ur|)1|¬Ek|¬En|)|4|≤m(k)/k
 5831  |g2|4α=↓|46/|≤p|g2|4α+↓|4O(1/n) (|πsee exercise 
 5834  4.5.2<10d); and |ε|¬K|ur|)1|¬Ek|¬En|)|4|≤m(k)|πlog 
 5837  |εk/k|g2|4α=↓|4O(1). |πHence |εh|βd(n)|4α=↓|4n(3|4|πln|42/|ε
 5839  |≤p|g2)|4|πln|ε(n/d)|4α+↓|4O(n) |πfor |εd|4|¬R|41. 
 5842  |πSo |εh(n)|4α=↓|42|4|¬K|ur|)cd|¬Dn|)|4|≤m(d)h|βc(n/cd)|4α=↓
 5843  |4{H11}({H9}(6|4|πln|42)/|ε|≤p|g2{H11}){H9}n(|πln|4|εn|4α_↓|
 5843  4|¬K|4α_↓|4|¬K|¬S)|4α+↓|4O(n|≤s|βα_↓|β1(n)|g2{H11}){H9}, 
 5844  |πwhere |ε|¬K|4α=↓|4|¬K|ur|)cd|¬Dn|)|4|≤m(d)|πln(|εcd)/cd|4α
 5845  =↓|40 |πand |ε|¬K|¬S|4α=↓|4|¬K|ur|)cd|¬Dn|)|4|≤m(d)|πln 
 5848  |εc/cd|4α=↓|4|¬K|ur|)d|¬Dn|)|4|*/|≤!|\(d)/d. |π[It 
 5850  is well known that |ε|≤s|βα_↓|β1(n)|4α=↓|4O(|πlog|4log|4|εn)
 5854  ; |πcf. Hardy and Wright, |εTheory of Numbers, 
 5862  |≤%22.9.]|'{A3}|π|≡3|≡5|≡.|4|9See ``Analysis 
 5865  of a subtractive algorithm,'' to appear.|'{H9L11M29}|≡3|≡6|≡
 5871  .|4|9Working the algorithm backwards, we want 
 5877  to choose |εk|β1,|4.|4.|4.|4,|4k|βn|βα_↓|β1 |πso 
 5881  that |εu|βk|4|"o|4F|βk|m1|4.|4.|4.|4F|βk|mi|mα_↓|m1F|βk|mi|β
 5882  α_↓|β1 {H11}({H9}|πmodulo gcd(|εu|βi|βα+↓|β1,|4.|4.|4.|4,|4u
 5884  |βn{H11}){H9} |πfor |ε1|4|¬E|4|¬W|4n, |πwith 
 5888  |εu|βn|4α=↓|4F|βk|m1|4.|4.|4.|4F|βk|mn|mα_↓|m1 
 5889  |πa minimum, where the |εk'|πs are positive, 
 5896  |εk|β1|4|¬R|43, |πand |εk|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4k
 5898  |βn|βα_↓|β1|4α=↓|4N|4α+↓|4n|4α_↓|41. |πThe solution 
 5901  is |εk|β2|4α=↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4k|βn|βα_↓|β1|4α=↓|42
 5902  , u|βn|4α=↓|4F|βN|βα_↓|βn|βα+↓|β3. [|πSee |εCACM 
 5906  |≡1|≡3 (1970), 433<436, 447<448.]|'{A3}{H9L11M29}|π|≡3|≡7|≡.
 5910  |4|9See |εProc. Amer. Math. Soc. |≡7 (1956), 
 5917  1014<1021; |πcf. exercise 6.1<18.|'{A3}|≡3|≡8|≡.|4|9Let 
 5922  |εm|4α=↓|4|"pn/|≤f|"P, |πso that |εm/n|4α=↓|4|≤f|gα_↓|g1|4α+
 5925  ↓|4|≤e|4α=↓|4|"Cx|β1,|4x|β2,|4.|4.|4.|4|"C |πwhere 
 5927  |ε0|4|¬W|4|≤e|4|¬W|41/n. |πLet |εk |πbe minimal 
 5932  such that |εx|βk|4α=↓|42; |πthen {H11}({H9}|ε|≤f|g1|gα_↓|gk|
 5936  4α+↓|4(|→α_↓1)|gkF|βk|βα_↓|β1|≤e{H11}){H9}/{H11}({H9}|≤f|gα_
 5936  ↓|gk|4α_↓|4(|→α_↓1)|gkF|βk|≤e{H11}){H9}|4|¬R|42, 
 5937  |πhence |εk |πis even and |ε|≤f|gα_↓|g2|4α=↓|42|4α_↓|4|≤f|4|
 5942  ¬E|4|≤f|gkF|βk|βα+↓|β2|≤e|4α=↓|4(|≤f|g2|gk|gα+↓|g2|4α_↓|4|≤f
 5942  |gα_↓|g2)|≤e/|¬H|v45|). [Ann. Polon. Math. |≡1 
 5947  (1954), 203<206.]|'{A3}{H9L11M29}|π|≡3|≡9|≡.|4|9At 
 5950  least 287 at bats; |"C2, 1, 95|"C|4α=↓|496/287|4α=↓|4.334494
 5956  77|4.|4.|4.|4, and no fraction with denominator 
 5962  |→|¬W287 lies in [.3335, .3345]|4α=↓|4[|"C2, 
 5967  1, 666|"C, |"C2, 1, 94, 1, 1, 3|"C].|'!!|1|1To 
 5976  solve the general question of the fraction in 
 5984  [9|εa, b] |πwith smallest denominator, where 
 5990  |ε0|4|¬W|4a|4|¬W|4b|4|¬W|41, |πnote that in terms 
 5995  of regular continued fraction representations 
 6000  we have |ε|"Cx|β1, x|β2,|4.|4.|4.|"C|4|¬W|4|"Cy|β1, 
 6004  y|β2,|4.|4.|4.|"C |πi= |ε(|→α_↓1)|gjy|βj |πfor 
 6008  the smmallest |εj |πwith |εx|βj|4|=|↔6α=↓|4y|βj, 
 6013  |πwhere we place ``|¬X'' after the last partial 
 6021  quotient of a rational number. Thus if |εa|4α=↓|4|"Cx|β1, 
 6029  x|β2,|4.|4.|4.|"C |πand |εb|4α=↓|4|"Cy|β1, y|β2,|4.|4.|4.|"C
 6032  , |πthe fractions in |ε[a, b] |πhave the form 
 6041  |εc|4α=↓|4|"Cx|β1,|4.|4.|4.|4,|4x|βj|βα_↓|β1, 
 6042  z|βj,|4.|4.|4.|4,|4z|βm|"C |πwhere |ε|"Cz|βj,|4.|4.|4.|4,|4z
 6044  |βm|"C |πlies between |ε|"Cx|βj, x|βj|βα+↓|β1,|4.|4.|4.|"C 
 6049  |πand |ε|"Cy|βj, y|βj|βα+↓|β1,|4.|4.|4.|"C |πinclusive. 
 6053  Let |εQ|βα_↓|β1|4α=↓|40. |πThe denominator |εQ|βj|βα_↓|β1(x|
 6057  β1,|4.|4.|4.|4,|4x|βj|βα_↓|β1)Q|βm|βα_↓|βj|βα+↓|β1(z|βj,|4.|
 6057  4.|4.|4,|4z|βm)|4α+↓|4Q|βj|βα_↓|β2(x|β1,|4.|4.|4.|4,|4x|βj|β
 6057  α_↓|β2)Q|βm|βα_↓|βj(z|βj|βα+↓|β1,|4.|4.|4.|4,|4z|βm) 
 6058  |πof |εc |πis minimized when |εm|4α=↓|4j |πand 
 6065  |εz|βj|4α=↓|4(j |πodd|4|"M|4|εy|βj|4α+↓|41|4α_↓|4|≤d|βy|mj|m
 6066  α+↓|m1|β|¬X; x|βj|4α+↓|41|4α_↓|4|≤d|βx|mj|mα+↓|m1|β|¬X).|'
folio 790 galley 10
 6068  |H{U0}{H9L11M29}58320#Computer Programming(Knuth/A.-W.)!f. 
 6070  790!ch. 4!g. 10c|'{A24}{H10L12M29}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|
 6073  ∨4|∨.|∨5|∨.|∨4|'{A12}{H9L11M29}|1|9|≡1|≡.|4|9If 
 6075  |εd|βk |πisn't prime, its prime factors are cost 
 6083  out before |εd|βk |πis tried.|'{A3}|9|1|≡2|≡.|4|9No, 
 6089  the alforithm would fail if |εp|βt|βα_↓|β1|4α=↓|4p|βt, 
 6095  |πgiving ``1'' as a spurious prime factor.|'{A3}|9|1|≡3|≡.|9
 6102  |4Let |εP |πbe the product of the _rst 168 primes. 
 6112  (|εNote|*/: |π|\Although |εP |πis a large number, 
 6119  it is considerably faster on many computers to 
 6127  calculate this gcd than to do the 168 divisions, 
 6136  if we just want to test whether or not |εn |πis 
 6147  prime.)|'{A3}|1|9|≡4|≡.|4|9Cf. exercise 3.1<11 
 6151  and Eq. 4.5.3<21; the average is asymptotically 
 6158  |ε|≤p|g2/12 |πtimes the average value of |ε|≤m|4α+↓|4|≤l, 
 6165  |πsince |εn|4α=↓|4|≤l|≤d|β|≤m|β0|4α+↓|4|≤m|4α+↓|4|≤l|4α_↓|41
 6166  |4α_↓|4{H11}({H9}(|≤m|4α+↓|4|≤l|4α_↓|41)|πmod|4|ε|≤l{H11}){H
 6166  9}.|'{A3}{H9L11M29}|1|9|≡5|≡.|4|9x|4|πmod 3|4α=↓|40; 
 6169  |εx|4|πmod|45|4α=↓|40, 1, 4; |εx|4|πmod|47|4α=↓|40, 
 6173  1, 6; |εx|4|πmod|48|4α=↓|41, 3, 5, 7; |εx|4|¬Q|4103. 
 6180  |πThe _rst try is |εx|4α=↓|4105: (105)|g2|4α_↓|410541|4α=↓|4
 6185  484|4α=↓|422|g2. |πThis would also have been 
 6191  found by Algorithm C in a relatively short time. 
 6200  Thus 10541|4α=↓|483|4|¬O|4127.|'{A3}|1|9|≡6|≡.|4|9Let 
 6203  us count the number of solutions |ε(x, y) |πof 
 6212  the congruence |εN|4|"o|4(x|4α_↓|4y)(x|4α+↓|4y) 
 6215  (|πmodulo |εp), |πwhere |ε0|4|¬E|4x, y|4|¬W|4p. 
 6220  |πSince |εN|4|=|↔6|"o|40 |πand |εp |πis prime, 
 6226  |εx|4α+↓|4y|4|=|↔6|"o|40. |πFor each |εv|4|=|↔6|"o|40 
 6230  |πthere is a unique |εu (|πmodulo |εp) |πsuch 
 6238  that |εN|4|"o|4uv. |πThe congruences |εx|4α_↓|4y|4|"o|4u, 
 6243  x|4α+↓|4y|4|"o|4v |πnow uniquely determine |εx 
 6248  |πmod |εp |πand |εy |πmod |εp, |πsince |εp |πis 
 6257  odd. Thus the stated congruence has exactly |εp|4α_↓|41 
 6265  |πsolutions (|εx,|4y). |πIf |ε(x,|4y) |πis a 
 6271  solution, so is |ε(x, p|4α_↓|4y) |πif |εy|4|=|↔6α=↓|40, 
 6278  |πsince (|εp|4α_↓|4y)|g2|4|"o|4y|g2; |πand if 
 6282  |ε(x, y|β1) |πand |ε(x, y|β2) |πare solutions 
 6289  with |εy|β1|4|=|↔6α=↓|4y|β2, |πwe have |εy|ur2|)1|)|4|"o|4y|
 6293  ur2|)2|); |πhence |εy|β1|4α=↓|4p|4α_↓|4y|β2. 
 6296  |πThus the number of di=erent |εx |πvalues among 
 6304  the solutions |ε(x, y) |πis |ε(p|4α_↓|41)/2 |πif 
 6311  |εN|4|"o|4x|g2 |πhas no solutions, or |ε(p|4α+↓|41)/2 
 6317  |πif |εN|4|"o|4x|g2 |πhas solutions.|'{A3}|9|1|≡7|≡.|4|9One 
 6322  procedure is to keep two indices for each modulus, 
 6331  one for the current word position and one for 
 6340  the current bit position; loading two words of 
 6348  the table and doing an indexed shift command 
 6356  will bring the table entries into proper alignment.|'
 6364  {A3}{H9L11M29}|1|9|≡8|≡.|4|9(We may assume that 
 6368  |εN|4α=↓|42M |πis even.) The following algorithm 
 6374  uses an auxiliary table |εX[1], X[2],|4.|4.|4.|4,|4X[M], 
 6380  |πwhere |εX[k] |πrepresents the primality of 
 6386  |ε2k|4α+↓|41.|'{A3}{I3H}|1|1!!|≡S|≡1|≡.|9|πSet 
 6388  |εX[k]|4|¬L|41 |πfor |ε1|4|¬E|4k|4|¬E|4M. |πAlso 
 6392  set |εj|4|¬L|41, p|4|¬L|41, p|4|¬L|43, q|4|¬L|44. 
 6397  (|πDuring this alforithm |εp|4α=↓|42j|4α+↓|41, 
 6401  q|4α=↓|42j|4α+↓|42j|g2; |πthe integer variables 
 6405  |εj, k, p, q |πmay readily be manipulated in 
 6414  index registers.)|'{A3}!!|1|1|≡S|≡2|≡.|9If |εX[j]|4α=↓|40, 
 6418  |πgo to S4. Otherwise output |εp, |πwhich is 
 6426  prime, and set |εk|4|¬L|4q.|'{A3}!!|1|1|π|≡S|≡3|≡.|9If 
 6431  |εk|4|¬E|4M, |πthen set |εX[k]|4|¬L|40, k|4|¬L|4k|4α+↓|4p, 
 6436  |πand repeat this step.|'{A3}|1|1!!|≡S|≡4|≡.|4|9Set 
 6441  |εj|4|¬L|4j|4α+↓|41, p|4|¬L|4p|4α+↓|42, q|4|¬L|4q|4α+↓|42p|4
 6443  α_↓|42. |πIf |εj|4|¬E|4M, |πreturn to S2.|'{A3}{IC}{H9L11M29
 6449  }A major part of this calculation could be made 
 6458  noticeably faster if |εq (|πinstead of |εj) |πwere 
 6466  tested against |εM |πin step S4, and if a new 
 6476  loop were appended which outputs |ε2j|4α+↓|41 
 6482  |πfor all remaining |εX[j] |πthat equal 1, suppressing 
 6490  the manipulation of |εp |πand |εq.|'{A3}|1|9|≡9|≡.|4|9|πIf 
 6497  |εp|g2 |πis a divisor of |εn |πfor some prime 
 6506  |εp, |πthen |εp |πis a divisor of |ε|≤l(n), |πbut 
 6515  not of |εn|4α_↓|41. |πIf |εn|4α=↓|4p|β1p|β2, 
 6520  |πwhere |εp|β1|4|¬W|4p|β2 |πare primes, then 
 6525  |εp|β2|4α_↓|41 |πis a divisor of |ε|≤l(n) |πand 
 6532  therefore |εp|β1p|β2|4α_↓|41|4|"o|40 {H11}({H9}|πmodulo 
 6535  (|εp|β2|4α_↓|41){H11}){H9}. |πSince |εp|β2|4|"o|41, 
 6538  p|β1|4α_↓|41 |πis a multiple of |εp|β2|4α_↓|41; 
 6544  |πbut this contradicts |εp|β1|4|¬W|4p|β2. {H11}({H9}|πValues
 6548   of |εn |πfor which |ε|≤l(n) |πproperly divides 
 6556  |εn|4α_↓|41 |πare called ``Carmichael numbers.'' 
 6561  See D. Shanks, |εSolved and Unsolved Problems 
 6568  in Number Theory |≡1 (|πWashington, D.C.: Spartan, 
 6575  1962), Sections 39<40.{H11}){H9}|'{A3}|≡1|≡0|≡.|4|9Let 
 6579  |εk|βp |πbe the order of |εx|βp |πmodulo |εn, 
 6587  |πand let |ε|≤l |πbe the least common multiple 
 6595  of all the |εk|βp'|πs. Then |ε|≤l |πis a divisor 
 6604  of |εn|4α_↓|41 |πbut not of any (|εn|4α_↓|41)/p, 
 6611  |πso |ε|≤l|4α=↓|4n|4α_↓|41. |πSince |εx|ur|≤'(n)|)p|) 
 6615  |πmod |εn|4α=↓|41, |≤'(n) |πis a multiple of 
 6622  |εk|βp |πfor all |εp, |πso |ε|≤'(n)|4|¬R|4|≤l. 
 6628  |πBut |ε|≤'(n)|4|¬W|4n|4α_↓|41 |πwhen |εn |πis 
 6633  not prime. (Another way to carry out the proof 
 6642  is to construct an element |εx |πof order |εn|4α_↓|41 
 6651  |πfrom the |εx|βp'|πs, by the method of exercise 
 6659  3.2.1.2<15.)|'{A3}|∂!!!|∂!!!|∂!!!|∂!!!!|∂!!|∂!!!|∂!!!!!!!|∂|
 6660  E|;|≡1|≡1|≡.|E|'|>|εU|;V|;A|;P|;S|;T|;|πOutput|;
 6670  >{A3}|>1984|4|4|?1|4|4|?0|4|4|?992|4|4|4|?0|4|4|4|?
 6677  #|4|4|?|;>|>1981|4|4|?1981|4|4|?1|4|4|?992|4|4|4|?
 6685  1|4|4|4|?1981|4|4|4|?|;>|>1983|4|4|?4|4|4|?495|4|4|?
 6693  993|4|4|4|?0|4|4|4|?1|4|4|?993|g2|4|"o|42|g2|4|4|4|?
 6697  >|>1983|4|4|?991|4|4|?2|4|4|?98109|4|4|4|?1|4|4|4|?
 6704  |;>|>1981|4|4|?4|4|4|?495|4|4|?2|4|4|4|?0|4|4|4|?
 6712  1|4|4|?2|g2|4|"o|42|g2|4|4|4|?>|>1984|4|4|?1981|4|4|?
 6718  1|4|4|?99099|4|4|4|?1|4|4|4|?1981|4|4|?|;>|>1984|4|4|?
 6726  1|4|4|?1984|4|4|?99101|4|4|4|?0|4|4|4|?1|4|4|?
 6731  99101|g2|4|"o|42|g0|4|4|4|?>{A7}{H9L11M29}The 
 6734  factorization 199|4|¬O|4991 is evident from the 
 6740  _rst or last outputs. The shortness of the cycle, 
 6749  and the appearance of the well-known number 1984, 
 6757  are probably just coincidences.|'{A3}|≡1|≡2|≡.|4|9The 
 6762  following algorithm makes use of an auxiliary 
 6769  |ε(m|4α+↓|41)|4α⊗↓|4(m|4α+↓|41) |πmatrix of single-precision
 6772   integers |εE|βj|βk, 0|4|¬E|4j, k|4|¬E|4m; |πa 
 6778  single-precision vector |ε(b|β0, b|β1,|4.|4.|4.|4,|4b|βm); 
 6782  |πand a multiple-precision vector |ε(x|β0, x|β1,|4.|4.|4.|4,
 6787  |4x|βm) |πwith entries in the range |ε0|4|¬E|4x|βk|4|¬W|4N.|
 6793  '{A3}{I3H}|π!!|1|1|≡F|≡1|≡.|9[Initialize.] Set 
 6796  |εb|βi|4|¬L|4|→α_↓1 |πfor |ε0|4|¬E|4i|4|¬E|4m; 
 6799  |πthen set |εj|4|¬L|40.|'!!|1|1|π|≡F|≡2|≡.|9[Next 
 6803  solution.] Get the next output (|εx, e|β0, e|β1,|4.|4.|4.|4,
 6810  |4e|βm |πproduced by Algorithm E. (It is convenient 
 6818  to regard Algorithms E and F as coroutines.) 
 6826  Set |εk|4|¬L|40.|'!!|1|1|π|≡F|≡3|≡.|9[Search 
 6829  for odd.] If |εk|4|¬Q|4m |πgo to step F5. Otherwise 
 6838  if |εe|βk |πis even, set |εk|4|¬L|4k|4α+↓|41 
 6844  |πand repeat this step.|'!!|1|1|≡F|≡4|≡.|9[Linear 
 6849  dependence?] If |εb|βk|4|¬R|40, |πthen set |εi|4|¬L|4b|βk, 
 6855  x|4|¬L|4(x|βix)|πmod |εN, e|βr|4|¬L|4e|βr|4α+↓|4E|βi|βr 
 6858  |πfor |ε0|4|¬E|4r|4|¬E|4m; |πset |εk|4|¬L|4k|4α+↓|41 
 6862  |πand return to F3. Otherwise set |εb|βk|4|¬L|4j, 
 6869  x|βj|4|¬L|4x, E|βj|βr|4|¬L|4e|βr |πfor |ε0|4|¬E|4r|4|¬E|4m; 
 6873  |πset |εj|4|¬L|4j|4α+↓|41 |πand return to F2. 
 6879  (In the latter case we have a new linearly independent 
 6889  solution, modulo 2, whose _rst odd component 
 6896  is |εe|βk.)|'!!|1|1|π|≡F|≡5|≡.|9[Try to factor.] 
 6901  (Now |εe|β0, e|β1,|4.|4.|4.|4,|4e|βm |πare even.) 
 6906  Set|'{A8}|εy|4|¬L|4{H11}({H9}(|→α_↓1) |ge|r0|g/|g2p|ure|β1/2
 6908  |)1|)|4.|4.|4.|4p|ure|βm/2|)m|){H11}){H9}|πmod|4|εN.|;
 6909  {A7}|π!!!!|1If |εx|4α=↓|4y |πor if |εx|4α+↓|4y|4α=↓|4N, 
 6914  |πreturn to F2. Otherwise compute gcd(|εx|4α_↓|4y, 
 6920  N), |πwhich is a proper factor of |εN, |πand 
 6929  terminate the algorithm.|'{A3}{IC}{H9L11M29}It 
 6933  can be shown that this algorithm _nds a factor, 
 6942  whenever one is deducible from the given outputs 
 6950  of Algorithm E.|'{A3}|≡1|≡3|≡.|4|9|εf|1(p,|4p|g2d)|4α=↓|42/(
 6953  p|4α+↓|41)|4α+↓|4f|1(p,|4d)/p, |πsince |ε1/(p|4α+↓|41) 
 6956  |πis the probability that |εA |πis a multiple 
 6964  of |εp. f|1(p,|4pd)|4α=↓|41/(p|4α+↓|41) |πwhen 
 6968  |εd|4|πmod|4|εp|4|=|↔6α=↓|40. f|1(2,|44k|4α+↓|43)|4α=↓|4|f1|
 6969  d33|) |πsince |εA|g2|4α_↓|4(4k|4α+↓|43)B|g2 |πcannot 
 6973  be a multiple of 4; |εf|1(2,|48k|4α+↓|45)|4α=↓|4|f2|d33|) 
 6979  |πsince |εA|g2|4α_↓|4(8k|4α+↓|45)B|g2 |πcannot 
 6982  be a multiple of 8; |εf|1(2,|48k|4α+↓|41)|4α=↓|4|f1|d33|)|4α
 6987  +↓|4|f1|d33|)|4α+↓|4|f1|d33|)|4α+↓|4|f1|d36|)|4α+↓|4|f1|d312
 6987  |)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4|f4|d33|). f|1(p,|4d)|4α=↓|
 6988  4(2p/(p|g2|4α_↓|41), 0{H11}){H9} |πif |εd|g(|gp|gα_↓|g1|g)|g
 6991  /|g2 |πmod |εp|4α=↓|4(1,|4p|4α_↓|41), |πrespectively, 
 6995  for odd |εp.|'{A3}|π|≡1|≡4|≡.|4|9Since |εP|g2|4|"o|4kNQ|g2 
 7000  (|πmodulo |εp) |πfor any prime divisor |εp |πof 
 7008  |εV, |πwe have 1|4|"o|4|εP|ur2(pα_↓1)/2|)|)|4|"o|4(kNQ|g2)|u
 7011  r(pα_↓1)/2|)|)|4|"o|4(kN)|ur(pα_↓1)/2|)|) (|πmodulo 
 7013  |εp), |πif |εP|4|=|↔6|"o|40.|'|H*?*?*?{U0}{H9L11M29}58320#Compu
folio 794 galley 11
 7016  ter Programming!(Knuth/A.-W.)!f. 794!ch. 4!g. 
 7020  11c|'{A12}|π|≡1|≡5|≡.|4|9|εU|βn|4α=↓|4(a|gn|4α_↓|4b|gn)/|¬H|
 7021  v4D|), |πwhere |εa|4α=↓|4|f1|d32|)(P|4α+↓|4|¬H|v4D|)), 
 7024  b|4α=↓|4|f1|d32|)(P|4α_↓|4|¬H|v4D|)), D|4α=↓|4P|g2|4α_↓|44Q.
 7025   |πThen |ε2|gn|gα_↓|g1U|βn|4α=↓|4|¬K|βk(|fn|d52kα+↓1|))P|gn|
 7027  gα_↓|g2|gk|gα_↓|g1D|gk; |πso |εU|βp|4|"o|4D|ur(pα_↓1)/2|)|) 
 7030  (|πmodulo |εp) |πif |εp |πis an odd prime. similarly, 
 7039  if |εV|βn|4α=↓|4a|gn|4α+↓|4b|gn|4α=↓|4U|βn|βα+↓|β1|4α_↓|4QU|
 7040  βn|βα_↓|β1, |πthen |ε2|gn|gα_↓|g1V|βn|4α=↓|4|¬K|βk 
 7043  (|fn|d52k|))P|gn|gα_↓|g2|gkD|gk, |πand |εV|βp|4|"o|4P|gn|4|"
 7045  o|4P. |πThus if |εU|βp|4|"o|4|→α_↓1, |πwe _nd 
 7051  that |εU|βp|βα+↓|β1 |πmod |εp|4α=↓|40. |πIf |εU|βp|4|"o|41, 
 7057  |πwe _nd that |ε(QU|βp|βα_↓|β1)|πmod |εp|4α=↓|40; 
 7062  |πhere if |εQ |πis a multiple of |εp, U|βn|4|"o|4P|gn|gα_↓|g
 7070  1 (|πmodulo |εp) |πfor |εn|4|¬Q|40, |πso |εU|βn 
 7077  |πis never a multiple of |εp; |πif |εQ |πis not 
 7087  a multiple of |εp, U|βp|βα_↓|β1 |πmod |εp|4α=↓|40. 
 7094  |πTherefore as in Theorem L, |εU|βt |πmod |εN|4α=↓|40 
 7102  |πif |εN|4α=↓|4p|ure|β1|)1|)|4.|4.|4.|4p|ure|βr|)r|), 
 7104  |πgcd(|εN, Q)|4α=↓|41, |πand |εt|4α=↓|4|πlcm|ur|)1|¬Ej|¬Er|)
 7107  {H11}({H9}p|ure|βjα_↓1|)j|)(p|βj|4α+↓|4|≤e|βj){H11}){H9}. 
 7108  |πUnder the assumptions of this exercise, the 
 7115  rank of apparition of |εN |πis |εN|4α+↓|41; |πhence 
 7123  |εN |πis prime to |εQ |πand |εt |πis a multiple 
 7133  of |εN|4α+↓|41. |πAlso, the assumptions of this 
 7140  exercise imply that each |εp|βj |πis odd and 
 7148  each |ε|≤e|βj |πis |→|¬N1, so |εt|4|¬E|42|g1|gα_↓|gr|4|≥7p|u
 7153  re|βjα_↓1|)j|)(p|βj|4α+↓|4|f1|d33|)p|βj)|4α=↓|42(|f2|d33|))|
 7153  grN; |πhence |εr|4α=↓|41 |πand |εt|4α=↓|4p|ure|β1|)1|)|4α+↓|
 7157  4|≤e|β1p|ure|β1α_↓1|)1|). |πFinally, therefore 
 7160  |εe|β1|4α=↓|41 |πand |ε|≤e|β1|4α=↓|41.|'!!|1|1Note|*/: 
 7164  |\|πObviously if this test for primality is to 
 7172  be any good, we must choose |εP |πand |εQ |πin 
 7182  some way which makes it likely that the test 
 7191  will work. Lehmer suggests taking |εP|4α=↓|41 
 7197  |πso that |εD|4α=↓|41|4α_↓|44Q, |πand choosing 
 7202  |εQ |πsi that gcd(|εN, QD)|4α=↓|41. (|πIf the 
 7209  latter condition fails, we know already that 
 7216  |εN |πis not prime, unless |ε|¬GQ|¬G|4|¬R|4N.) 
 7222  |πFurthermore, the derivation above shows that 
 7228  we will want |ε|≤e|β1|4α=↓|41, |πthat is, |εD|ur(Nα_↓1)/2|)|
 7234  )|4|"o|4|→α_↓1 (|πmodulo |εN). |πThis is another 
 7240  condition which determines the choice of |εQ. 
 7247  |πFurthermore, if |εD |πsatis_es this condition, 
 7253  and if |εU|βN|βα+↓|β1 |πmod |εN|4|=|↔6α=↓|40, 
 7258  |πwe know that |εN |πis |εnot |πprime.|'!!|1|1|εExample|*/: 
 7266  |\|πIf |εP|4α=↓|41, Q|4α=↓|4|→α_↓1, |πwe have 
 7271  the Fibonacci sequence, with |εD|4α=↓|45. |πSince 
 7277  5|g1|g1|4|"o|4|→α_↓1 (modulo 23), we might attempt 
 7283  to prove that 23 is prime by using the Fibonacci 
 7293  sequence:|'{A8}|ε|↔bF|βn |πmod 23|↔v|4α=↓|40, 
 7297  1, 1, 2, 3, 5, 8, 13, 21, 11, 9, 20, 6, 3, 9, 
 7311  12, 21, 10, 8, 18, 3, 21, 1, 22, 0, . . .|;{A9}{H9L11M29}so 
 7325  24 is the rank of apparition of 23 and the test 
 7336  works. However, the Fibonacci sequence cannot 
 7342  be used in this way to prove the primality of 
 7352  13 or 17, since |εF|β7 |πmod 13|4α=↓|40 |πand 
 7360  |εF|β9 |πmod 17|4α=↓|40. When |εp|4|"o|4|→|¬N1 
 7365  (|πmodulo 10), we have 5|ur|ε(pα_↓1)/2|)|) |πmod 
 7371  |εp|4α=↓|41, |πso |εF|βp|βα_↓|β1 |π(not |εF|βp|βα+↓|β1) 
 7376  |πis divisible by |εp.|'{A3}|π|≡1|≡3|≡.|4|9Let 
 7381  |εf|1(q)|4α=↓|42|4|πlg|4|εq|4α_↓|41. |πWhen |εq|4α=↓|42 
 7384  |πor 3, the tree has at most |εf|1(q) |πnodes. 
 7393  When |εq|4|¬Q|43 |πis prime, let |εq|4α=↓|41|4α+↓|4q|β1|β1|4
 7398  .|4.|4.|4q|βt |πwhere |εt|4|¬R|42 |πand |εq|β1,|4.|4.|4.|4,|
 7402  4q|βt |πare prime. The size of the tree is |ε|→|¬E1|4α+↓|4|¬
 7411  K|4f(q|βk)|4α=↓|42|4α+↓|4f|1(q|4α_↓|41)|4α_↓|4t|4|¬W|4f|1(q)
 7411  . [Siam J. Comp. |≡7 (1975), 214<220.]|'{A3}|≡1|≡8|≡.|4|9|εx
 7418  {H11}({H9}G(|≤a)|4α_↓|4F(|≤a){H11}){H9} |πis 
 7420  the number of |εn|4|¬E|4x |πwhose second-largest 
 7426  prime factor is |→|¬E|εx|g|≤a |πand whose largest 
 7433  prime factor is |ε|→|¬Qx|g|≤a. |πHence |εxG|¬S(t)|4dt|4α=↓|4
 7438  {H11}({H9}|≤p(x|gt|gα+↓|gd|gt)|4α_↓|4|≤p(x|gt){H11}){H9}. 
 7439  x|g1|gα_↓|gt{H11}({H9}G(t/(1|4α_↓|4t){H11}){H9}|4α_↓|4F{H11}
 7439  ({H9}t/(1|4α_↓|4t)){H11}){H9}. |πThe probability 
 7442  that |εp|βt|βα_↓|β1|4|¬E|4|¬H|v4p|βt|) |πis |¬J|ur1|)0|)|4|ε
 7445  F{H11}({H9}t/2(1|4α_↓|4t){H11}){H9}t|gα_↓|g1|4dt. 
 7446  [|πNumerical evaluation yields .62433. Curiously, 
 7451  it can be shown that this also equals |ε|¬J|ur1|)0|)|4F{H11}
 7459  ({H9}t/(1|4α_↓|4t){H11}){H9}|4dt, |πthe average 
 7462  value of log |εp|βt/|πlog |εx. |πThe derivative 
 7469  |εG|¬S(0) |πcan be shown to equal |ε|¬J|ur1|)0|)|4F{H11}({H9
 7475  }t/(1|4α_↓|4t){H11}){H9}t|gα_↓|g2|4dt|4α=↓|4F(1)|4α+↓|42F(|f
 7475  1|d32|))|4α+↓|43F(|f1|d33|))|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|41
 7475  .78107. |πThe third-largest prime factor has 
 7481  |εH(|≤g)|4α=↓|4|¬J|ur|≤g|)0|)|4{H11}({H9}H(t/(1|4α_↓|4t))|4α
 7481  _↓|4G(t/(1|4α_↓|4t)){H11}){H9}t|gα_↓|g1|4dt |πand 
 7483  |εH|¬S(0)|4α=↓|4|¬X. |πSee D. E. Knuth and L. 
 7490  Trabb-Pardo, to appear.]|'{A3}|≡1|≡9|≡.|4|9|εM|4α=↓|42|gD|4α
 7493  _↓|41 |πis a multiple of all |εp |πfor which 
 7502  the order of 2 modulo |εp |πdivides |εD. |πLet 
 7511  |εa|β1|4α=↓|42 |πand |εa|βj|βα+↓|β1|4α=↓|4a|urq|βj|)j|) 
 7514  |πmod |εN, |πwhere |εq|βj|4α=↓|4p|ure|βj|)j|), 
 7518  p|βj |πis the |εj|πth prime, and |εe|βj|4α=↓|4|"l|πlog|41000
 7524  /log|4|εp|βj|"L; |πlet |εA|4α=↓|4a|β1|β6|β9. 
 7527  |πNow compute |εb|βq|4α=↓|4|πgcd(|εA|gq|4α_↓|41, 
 7530  N) |πfor all primes |εq |πbetween 10|g3 and 10|g5. 
 7539  One way to do this is to start with |εA|g1|g0|g0|g9 
 7549  |πmod |εN |πand then to multiply alternately 
 7556  by |εA|g4 |πmod |εN |πand |εA|g2 |πmod |εN. (|πA 
 7565  similar method was used in the 1920's by D. N. 
 7575  Lehmer, but he didn't publish it.) As with Algorithm 
 7584  B we can avoid most of the gcd's by batching; 
 7594  e.g., since |εb|β3|β0|βα_↓|βk|4α=↓|4|πgcd(|εA|g3|g0|gr|4α_↓|
 7596  4A|gk, N) |πwe might try batches of 8, computing 
 7605  |εc|βr|4α=↓|4(A|g3|g0|gr|4α_↓|4A|g2|g9)(A|g3|g0|gr|4α_↓|4A|g
 7605  2|g3)|4.|4.|4.|4(A|g3|g0|gr|4α_↓|4A) |πmod |εN, 
 7608  |πthen gcd(|εc|βr, N) |πfor 33|4|¬W|4|εr|4|¬E|43334.|'
 7613  {A24}{H10L12M29}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|4|∨4|∨.|∨6|'
 7614  {A12}{H9L11M29}|1|9|≡1|≡.|4|9|ε9x|g2|4α+↓|47x|4α+↓|49; 
 7615  5x|g3|4α+↓|47x|g2|4α+↓|42x|4α+↓|46.|'{A3}|1|9|≡2|≡.|4|9|π(a)
 7616   True. (b) False if the algebraic system |εS 
 7625  |πcontains ``zero divisors'', nonzero numbers 
 7630  whose product is zero, as in exercise 1; otherwise 
 7639  true. (c) False; (|εx|4α+↓|41)|4α+↓|4{H11}({H9}(|→α_↓1)x|4α+
 7642  ↓|40{H11}){H9}|4α=↓|41.|'{A3}{H9L11M29}|1|9|≡3|≡.|4|9|πAssum
 7643  e that |εr|4|¬E|4s. |πFor |ε0|4|¬E|4k|4|¬E|4r 
 7648  |πthe maximum is |εm|β1m|β2(k|4α+↓|41); |πfor 
 7653  |εr|4|¬E|4k|4|¬E|4s |πit is |εm|β1m|β2(r|4α+↓|41); 
 7657  |πfor |εs|4|¬E|4k|4|¬E|4r|4α+↓|4s |πit is |εm|β1m|β2(r|4α+↓|
 7661  4s|4α+↓|41|4α_↓|4k). |πThe least upper bound 
 7666  valid for all |εk |πis |εm|β1m|β2(r|4α+↓|41). 
 7672  (|πThe solver of this exercise will know how 
 7680  to factor the polynomial |εx|g7|4α+↓|42x|g6|4α+↓|43x|g5|4α+↓
 7684  |43x|g4|4α+↓|43x|g3|4α+↓|43x|g2|4α+↓|42x|4α+↓|41.)|'
 7685  {A3}|1|9|≡4|≡.|4|9|πIf the polynomials each have 
 7690  less than 2|ε|gt |πnonzero coe∃cients, the product 
 7697  can be formed by putting exactly |εt|4α_↓|41 
 7704  |πzeros between each of the coe∃cients, then 
 7711  multiplying in the binary number system, and 
 7718  _nally using a logical |¬a|¬n|¬d operation (present 
 7725  on most binary computers, cf. Section 4.5.4) 
 7732  to zero out the extra bits. For example if |εt|4α=↓|43, 
 7742  |πthe multiplication in the text would become 
 7749  (1001000001)|β2|4α⊗↓|4(1000001001)|β2 α=↓ (100-00-0--00-00-0
 7751  0-)|β2; |πif we |¬a|¬n|¬d the result with the 
 7759  constant (1001001|4.|4.|4.|41001)|β2, the desired 
 7763  answer is obtained. A similar technique can be 
 7771  used to multiply polynomials with nonnegative 
 7777  coe∃cients when it is known that the coe∃cients 
 7785  will not be too large.|'{A3}|1|9|≡5|≡.|4|9Polynomials 
 7791  of degree |ε|→|¬E2n |πcan be represented as |εU|β1(x)x|gn|4α
 7798  +↓|4U|β0(x) |πwhere deg (|εU|β1), |πdeg |ε(U|β0)|4|¬E|4n; 
 7804  |πand |ε{H11}({H9}U|β1(x)x|gn|4α+↓|4U|β0(x){H11})({H9}V|β1(x
 7805  )x|gn|4α+↓|4V|β0(x){H11}){H9}|4α=↓|4U|β1(x)V|β1(x)(x|g2|gn|4
 7805  α+↓|4x|gn)|4α+↓|4{H11}({H9}U|β1(x)|4α+↓|4U|β0(x){H11})({H9}V
 7805  |β1(x)|4α+↓|4V|β0(x){H11}){H9}x|gn|4α+↓|4U|β0(x)V|β0(x)(x|gn
 7805  |4α+↓|41). (|πThis equation assumes that arithmetic 
 7811  is being done modulo 2.) Thus Eqs. 4.3.3<3, 4, 
 7820  5 hold.|'|ε!!|1|1Note|*/: |\|πS. A. Cook has shown 
 7828  that Algorithm 4.3.3C can be extended in a similar 
 7837  way, and exercise 4.6.4<14 describes a method 
 7844  requiring even fewer operations for large |εn. 
 7851  |πBut these ideas are not useful for ``sparse'' 
 7859  polynomials (having mostly zero coe∃cients).|'
 7864  {A24}{H10L12M29}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|4|∨4|∨.|∨6|∨.|∨1|'
 7865  {A12}{H9L11M29}|1|9|≡1|≡.|4|9|εQ(X)|4α=↓|41|4|¬O|42|g3x|g3|4
 7865  α+↓|40|4|¬O|42|g2x|g2|4α_↓|42|4|¬O|42x|4α+↓|48|4α=↓|48x|g3|4
 7865  α_↓|44x|4α+↓|48; r(x)|4α=↓|428x|g2|4α+↓|44x|4α+↓|48.|'
 7867  {A3}|π|1|9|≡2|≡.|4|9The monic sequence of polynomials 
 7872  produced during Euclid's algorithm has the coe∃cients 
 7879  (1, 5, 6, 6, 1, 6, 3), (1, 2, 5, 2, 2, 4, 5), 
 7893  (1, 5, 6, 2, 3, 4), (1, 3, 4, 6), 0. Hence the 
 7906  greatest common divisor is |εx|g3|4α+↓|43x|g2|4α+↓|44x|4α+↓|
 7910  46. |π(The greatest common divisor of a polynomial 
 7918  and its reverse is always symmetric, in the sense 
 7927  that it is a unit multiple of its own reverse.)|'
 7937  {A3}|1|9|≡3|≡.|4|9The procedure of Algorithm 
 7941  4.5.2X is valid, with polynomials over |εS |πsubstituted 
 7949  for integers. When the algorithm terminates, 
 7955  we have |εU(x)|4α=↓|4u|β2(x), V(x)|4α=↓|4u|β1(x). 
 7959  |πLet |εm|4α=↓|4|πdeg|ε(u), n|4α=↓|4|πdeg|ε(v). 
 7962  |πIt is easy to prove by induction that deg(|εu|β3)|4α+↓|4|π
 7970  deg(|εv|β1)|4α=↓|4n, |πdeg|ε(u|β3)|4α+↓|4|πdeg|ε(v|β2)|4α=↓|
 7971  4m, |πafter step X3, throughout the execution 
 7978  of the algorithm, provided that |εm|4|¬R|4n. 
 7984  |πHence if |εm |πand |εn |πare greater than |εd|4α=↓|4|πdeg{
 7992  H11}({H9}gcd(|εu,|4v){H11}){H9} |πwe have deg(|εU)|4|¬W|4m|4
 7995  α_↓|4d, |πdeg(|εV)|4|¬W|4n|4α_↓|4d; |πthe exact 
 7999  degrees are |εm|4α_↓|4d|β1 |πand |εn|4α_↓|4d|β1, 
 8004  |πwhere |εd|β1 |πis the degree of the second-last 
 8012  nonzero remainder. If |εd|4α=↓|4|πmin|ε(m, n), 
 8017  |πsay |εd|4α=↓|4n, |πwe have |εU(x)|4α=↓|40, 
 8022  V(x)|4α=↓|41.|'|π!!|1|1When |εu(x)|4α=↓|4x|gm|4α_↓|41 
 8025  |πand |εv(x)|4α=↓|4x|gn|4α_↓|41, |πthe identity 
 8029  |ε(x|gm|4α_↓|41)|πmod|ε(x|gn|4α_↓|41)|4α=↓|4x|gm|1|1|π|gm|go
 8029  |gd|1|1|ε|gn|4α_↓|41 |πshows that all polynomials 
 8034  occurring during the calculation are monic with 
 8041  integer coe∃cients. When |εu(x)|4α=↓|4x|g2|g1|4α_↓|41, 
 8045  v(x)|4α=↓|4x|g1|g3|4α_↓|41, |πwe have |εV(x)|4α=↓|4(x|g1|g1|
 8048  4α+↓|4x|g8|4α+↓|4x|g6|4α+↓|4x|g3|4α+↓|41), U(x)|4α=↓|4|→α_↓(
 8049  x|g1|g9|4α+↓|4x|g1|g6|4α+↓|4x|g1|g4|4α+↓|4x|g1|g1|4α+↓|4x|g8
 8049  |4α+↓|4x|g6|4α+↓|4x|g3|4α+↓|4x). |π[See also 
 8052  Eq. 3.3.3<29, which gives an alternative formula 
 8059  for |εU(x), V(x).]|'|H*?*?{U0}{H9L11M29}58320#Computer 
folio 797 galley 12
 8063  Programming!(Knuth/A.-W.)!f. 797!ch. 4!g 12c|'
 8067  {A12}|π|1|9|≡4|≡.|9|4Since the quotient |εq(x) 
 8071  |πdepends only on |εv(x) |πand the _rst |εm|4α_↓|4n 
 8079  |πcoe∃cients of |εu(x), |πthe remainder |εr(x)|4α=↓|4u(x)|4α
 8084  _↓|4q(x)v(x) |πis uniformly distributed and independent 
 8090  of |εv(x). |πHence each step of the algorithm 
 8098  may be regarded as independent of the others; 
 8106  this algorithm is much more well-behaved than 
 8113  Euclid's algorithm over the integers.|'!!|1|1The 
 8119  probability that |εn|β1|4α=↓|4n|4α_↓|4k |πis 
 8123  |εp|g1|gα_↓|gk(1|4α_↓|41/p), |πand |εt|4α=↓|40 
 8126  |πwith probability |εp|gα_↓|gn. |πEach succeeding 
 8131  step has essentially the same behavior; hence 
 8138  we can see that any given sequence of degrees 
 8147  |εn, n|β1,|4.|4.|4.|4,|4n|βt, |→α_↓|¬X |πoccurs 
 8151  with probability |ε(p|4α_↓|41)|gt/p|gn. |πTo 
 8155  _nd the average value of |εf|1(n|β1,|4.|4.|4.|4,|4n|βt), 
 8161  |πlet |εS|βt |πbe the sum of |εf|1(n|β1,|4.|4.|4.|4,|4n|βt) 
 8168  |πover all sequences |εn|4|¬Q|4n|β1|4|¬Q|1|1|¬O|4|¬O|4|¬O|1|
 8171  1|¬Q|4n|βt|4|¬R|40 |πhaving a given value of 
 8177  |εt; |πthen the average is |ε|¬K|βt|4S|βt(p|4α_↓|41)|gt/p|gn
 8182  .|'{H9L11M29}!!|1|1Let |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)|4α=↓|4
 8184  t; |πthen |εS|βt|4α=↓|4(|urn|)t|))(t|4α+↓|41), 
 8187  |πso the average is |εn(1|4α_↓|41/p). |πSimilarly, 
 8193  if |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)|4α=↓|4n|β1|4α+↓|1|1|¬O|4|¬
 8194  O|4|¬O|1|1α+↓|4n|βt, |πthen |εS|βt|4α=↓|4(|urn|)2|))(|urnα_↓
 8196  1|)tα_↓1|)), |πand the average is |ε(|urn|)2|))(1|4α_↓|41/p)
 8201  . |πFinally, if |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)|4α=↓|4(n|4α_↓
 8204  |4n|β1)n|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4(n|βt|βα_↓|β1|4α_↓
 8204  |4n|βt)n|βt |πthen |εS|βt|4α=↓|4(|urnα+↓2|)tα+↓2|))|4α_↓|4(n
 8206  |4α+↓|41)(|urnα+↓1|)tα+↓1|))|4α+↓|4(|urnα+↓1|)|92|))(|urn|)t
 8206  |)), |πand the average is (|ε|urnα+↓1|)|92|))|4α_↓|4(n|4α+↓|
 8211  41)p/(p|4α_↓|41)|4α+↓|4{H11}({H9}p/(p|4α_↓|41){H11}){H9}|g2(
 8211  1|4α_↓|41/p|gn|gα+↓|g1).|'|π!!|1|1As a consequence 
 8215  we can see that if |εp |πis large there is very 
 8226  high probability that |εn|βj|βα+↓|β1|4α=↓|4n|βj|4α_↓|41 
 8230  |πfor all |εj. |π(If this condition fails over 
 8238  the rational numbers, it fails for all |εp, |πso 
 8247  we have further evidence for the text's claim 
 8255  that Algorithm C almost always _nds |εt|β3|4α=↓|1|1|¬O|4|¬O|
 8261  4|¬O|1|1α=↓|42.)|'{U0}{H9L11M29}{A3}|π|1|9|≡5|≡.|4|9Using 
 8263  the formulas developed in exercise 4, with |εf|1(n|β1,|4.|4.
 8270  |4.|4,|4n|βt)|4α=↓|4|≤d|βn|mt|β0, |πwe _nd the 
 8274  probability is |ε1|4α_↓|41/p |πif |εn|4|¬Q|40, 
 8279  1 |πif |εn|4α=↓|40.|'{A3}|π|1|9|≡6|≡.|4|9Assuming 
 8283  that the constant terms |εu(0) |πand |εv(0) |πare 
 8291  nonzero, imagine a ``right-to-left'' division 
 8296  algorithm, |εu(x)|4α=↓|4v(x)q(x)|4α+↓|4x|gm|gα_↓|gnr(x), 
 8298  |πdeg|ε(r)|4|¬W|4|πdeg|ε(v). |πWe obtain a gcd 
 8303  algorithm anlogous to Algorithm 4.5.2B, which 
 8309  is essentially Euclid's algorithm applied to 
 8315  the ``reverse'' of the original inputs (cf. exercise 
 8323  2), afterwards reversing the answer and multiplying 
 8330  by an appropriate power of |εx.|'{A3}|π|1|9|≡7|≡.|4|9The 
 8337  units of |εS |π(as polynomials of degree zero).|'
 8345  {A3}|1|9|≡8|≡.|4|9If |εu(x)|4α=↓|4v(x)w(x), |πwhere 
 8348  |εu(x) |πhas integer coe∃cients while |εv(x) 
 8354  |πand |εw(x) |πhave rational coe∃cients, there 
 8360  are integers |εm |πand |εn |πsuch that |εm|4|¬0|4v(x) 
 8368  |πand |εn|4|¬O|4w(x) |πhave integer coe∃cients. 
 8373  Now |εu(x) |πis primitive, so we have|'{A9}|εu(x)|4α=↓|4|¬N|
 8380  πPP{H11}({H9}|εm|4|¬0|4v(x){H11}){H9}|πpp{H11}({H9}|εn|4|¬O|
 8380  4w(x){H11}){H9}.|;{A9}|π|9|1|≡9|≡.|4|9We can 
 8383  extend Algorithm E as follows: Let {H11}({H9}|εu|β1(x), 
 8390  u|β2(x), u|β3, u|β4(x){H11}){H9} |πand {H11}({H9}|εv|β1(x), 
 8395  v|β2(x), v|β3, v|β4(x){H11}){H9}|πbe quadruples 
 8399  satisfying the relations |εu|β1(x)u(x)|4α+↓|4u|β2(x)v(x)|4α=
 8402  ↓|4u|β3u|β4(x), v|β1(x)u(x)|4α+↓|4v|β2(x)v(x)|4α=↓|4v|β3v|β4
 8403  (x). |πThe extended algorithm starts with {H11}({H9}1, 
 8410  0, cont|ε(u), |πpp(|εu(x)){H11}){H9} |πand {H11}({H9}0, 
 8415  1, cont(|εv), |πpp|ε(v(x)){H11}){H9} |πand manipulates 
 8420  these quadruples in such a way as to preserve 
 8429  the above conditions, where |εu|β4(x), v|β4(x) 
 8435  |πrun through the same sequence as |εu(x), v(x) 
 8443  |πdo in Algorithm E. If |εau|β4(x)|4α=↓|4q(x)v|β4(x)|4α+↓|4b
 8448  r(x), |πwe have |εav|β3{H11}({H9}u|β1(x), u|β2(x){H11}){H9}|
 8452  4α_↓|4q(x)u|β3{H11}({H9}v|β1(x), v|β2(x){H11}){H9}|4α=↓|4{H1
 8453  1}({H9}r|β1(x), r|β2(x){H11}){H9}, |πwhere |εr|β1(x)u(x)|4α+
 8456  ↓|4r|β2(x)v(x)|4α=↓|4bu|β3v|β3r(x), |πso the 
 8459  extended algorithm can preserve the desired relations. 
 8466  If |εu(x) |πand |εv(x) |πare relatively prime, 
 8473  the extended algorithm eventually _nds |εr(x) 
 8479  |πof degree zero, and we obtain |εU(x)|4α=↓|4r|β2(x), 
 8486  V(x)|4α=↓|4r|β1(x) |πas desired. (In practice 
 8491  we would divide |εr|β1(x), r|β2(x), |πand |εbu|β3v|β3 
 8498  |πby gcd{H11}({H9}cont|ε(r|β1), |πcont(|εr|β2)).{H11}){H9} 
 8501  |πConversely, if such |εU(x) |πand |εV(x) |πexist, 
 8508  then |εu(x) |πand |εv(x) |πhave no common prime 
 8516  divisors, since they are primitive and have no 
 8524  common divisors of positive degree.|'{A3}{H9L11M29}|≡1|≡0|≡.
 8529  |4|9By successively factoring polynomials which 
 8534  are reducible into polynomials of smaller degree, 
 8541  we must obtain a _nite factorization of any polynomial 
 8550  into irreducibles. The factorization of the |εcontent 
 8557  |πis unique. To show that there is at most one 
 8567  factorization of the primitive part, the key 
 8574  result is to prove that if |εu(x) |πis an irreducible 
 8584  factor of |εv(x)w(x), |πbut not a unit multiple 
 8592  of the irreducible polynomial |εv(x), |πthen 
 8598  |εu(x) |πis a factor of |εw(x). |πThis can be 
 8607  proved by observing that |εu(x) |πis a factor 
 8615  of |εv(x)w(x)U(x)|4α=↓|4rw(x)|4α_↓|4w(x)u(x)V(x) 
 8617  |πby the result of exercise 9, where |εr |πis 
 8626  a nonzero constant.|'{A3}{H9L11M29}|≡1|≡1|≡.|4|9The 
 8630  only row names needed to show that |εu|β4(x) 
 8638  |πhas integer coe∃cients are |εA|β1, A|β0, B|β4, 
 8645  B|β3, B|β2, B|β1, B|β0, C|β1, C|β0, D|β0. |πIn 
 8653  general, let |εu|βj|βα+↓|β2(x)|4α=↓|40; |πthen 
 8657  the rows needed for the proof are |εA|βn|m2|βα_↓|βn|mj 
 8665  |πthrough |εA|β0, C|βn|m2|βα_↓|βn|mj |πthrough 
 8669  |εC|β0, D|βn|m3|βα_↓|βn|mj |πthrough |εD|β0, 
 8673  |πetc.|'{A3}|≡1|≡2|≡.|4|9If |εn|βk|4α=↓|40, |πthe 
 8677  argument in the text can be modi_ed to show that 
 8687  the absolute value of the determinant is |ε|λ3|urn|βk|βα_↓|β
 8694  1|)k|)/|≥7|ur|)1|¬Wj|¬Wk|)|4|λ3|ur(t|βjα_↓1)(t|βj|βα+↓|β1α_↓
 8694  2)|)j|). |πIf the polynomials have a factor of 
 8702  positive degree, we can arti_cially assume that 
 8709  the polynomial zero has degree zero and use the 
 8718  above formula for |ε|λ3|βk|4α=↓|40. Note|*/: |\|πThe 
 8724  value |εR(u,|4v) |πof Sylvester's determinant 
 8729  is called the |εresultant |πof |εu |πand |εv, 
 8737  |πand the quantity (|→α_↓1)|urdeg|ε(u)(|πdeg(|εu)α_↓1)/2|)|)
 8740  |4|λ3(u)|gα_↓|g1R(u,|4u|¬S) |πis called the |εdiscriminant 
 8745  |πof |εu. |πIf |εu(x)|4α=↓|4a(x|4α_↓|4|≤a|β1)|4.|4.|4.|4(x|4
 8748  α_↓|4|≤a|βm) |πand |εv(x)|4α=↓|4b(x|4α_↓|4|≤b|β1)|4.|4.|4.|4
 8750  (x|4α_↓|4|≤b|βn), |πwe have |εR(u,|4v)|4α=↓|4a|gnv(|≤a|β1)|4
 8753  .|4.|4.|4v(|≤a|βm)|4α=↓|4(|→α_↓1)|gm|gnb|gmu(|≤b|β1)|4.|4.|4
 8753  .|4u(|≤b|βn)|4α=↓|4a|gnb|gm|4|≥7|ur|)1|¬Ei|¬Em,1|¬Ej|¬En|)(|
 8753  ≤a|βi|4α_↓|4|≤b|βj). |πIt follows that the polynomials 
 8759  of degree |εmn |πin |εy |πde_ned as the respective 
 8768  resultants of |εu(y|4α_↓|4x), u(y|4α+↓|4x), x|gmu(y/x), 
 8773  |πand |εu(yx) |πwith |εv(x) |πhave as respective 
 8780  roots the sums |ε|≤a|βi|4α+↓|4|≤b|βj, |πdi=erences 
 8785  |ε|≤a|βi|4α_↓|4|≤b|βj, |πproducts |ε|≤a|βi|≤b|βj, 
 8788  |πand quotients |ε|≤a|βi/|≤b|βj {H11}({H9}|πwhen 
 8792  |εv(0)|4|=|↔6α=↓|40{H11}){H9}. |πThis idea has 
 8796  been used by R. G. K. Loos to construct algorithms 
 8806  for arithmetic on algebraic numbers [|εSIAM J. 
 8813  Computing |≡5 (1976), |πto appear].|'!!|1|1If 
 8819  we replace each row |εA|βi |πin Sylvester's matrix 
 8827  by|'{A8}|ε(b|β0A|βi|4α+↓|4b|β1A|βi|βα+↓|β1|4α+↓|1|1|¬O|4|¬O|
 8828  4|¬O|1|1α+↓|4b|βn|m2|βα_↓|β1|βα_↓|βiA|βn|m2|βα_↓|β1) 
 8829  α_↓ (a|β0B|βi α+↓ a|β1B|βi|βα+↓|β1 α+↓ |¬O |¬O 
 8836  |¬O α+↓ a|βn|m2|βα_↓|β1|βα_↓|βiB|βn|m2|βα_↓|β1),|;
 8839  {A9}|π{H9L11M29}and then delete rows B|βn|m2|βα_↓|β1 
 8844  |πthrough |εB|β0 |πand the last |εn|β2 |πcolumns, 
 8851  we obtain an |εn|β1|4α⊗↓|4n|β1 |πdeterminant 
 8856  for the resultant instead of the original |ε(n|β1|4α+↓|4n|β2
 8863  )|4α⊗↓|4(n|β1|4α+↓|4n|β2) |πdeterminant. In some 
 8867  cases the resultant can be evaluated e∃ciently 
 8874  by means of this determinant; see |εCACM |≡1|≡2 
 8882  (1969), 23<30, 302<303.|'{A3}{H9L11M29}|π|≡1|≡3|≡.|4|9If 
 8886  |ε|λ3|urt|βk|)k|)u|βk|βα_↓|β1(x)|4α=↓|4u|βk(x)q|βk|βα_↓|β1(x
 8886  )|4α+↓|4|λ3|urt|βk|βα_↓|β1|)kα_↓1|)u|βk|βα+↓|β1(x) 
 8887  |πthen (|ε|λ3|βk|λ3|gx|r|gα+↓|g1)|gt|rk|λl|urx|βk|βα_↓|β1|)|
 8888  )w(x)u|βk|βα_↓|β1(x)|4α=↓|4|λ3|gx|rkw(x)u|βk(x)|λ3|gy|rkq(x)
 8888  |4α+↓|4(|λ3|βk|βα_↓|β1|λ3|urx|βk|βα_↓|β1α+↓1|)|))|urt|βk|βα_
 8888  ↓|β1|)|)|λ3|urx|βk|βα+↓|β1|)|)w(x)u|βk|βα+↓|β1(x); 
 8889  |πso the new |εu|βk(x) |πis |ε|λ3|urx|βk|)|)w(x)u|βk(x), 
 8895  |πwhere |εx|β1|4α=↓|4x|β2|4α=↓|4t|β1|4α=↓|40, 
 8897  x|βk|βα+↓|β1|4α=↓|4x|βkt|βk|4α_↓|4x|βk|βα_↓|β1(t|βk|βα_↓|β1|
 8897  4α_↓|41)|4α+↓|4t|βk|4α_↓|4t|βk|βα_↓|β1.|'{A3}|π|≡1|≡4|≡.|4|9
 8898  Let |εp |πbe a prime of the domain, and let |εj,k 
 8909  |πbe maximum such that |εp|gk|¬Dv|βn|4α=↓|4|λ3(v), 
 8914  p|gj|¬Dv|βn|βα_↓|β1. |πLet |εP|4α=↓|4p|gk. |πBy 
 8918  Algorithm R we may write |εq(x)|4α=↓|4a|β0|4α+↓|4Pa|β1x|4α+↓
 8923  |1|1|¬O|4|¬O|4|¬O|1|1α+↓|4P|gsa|βsx|gs, |πwhere 
 8925  |εs|4α=↓|4m|4α_↓|4n|4|¬R|42. |πLet us look at 
 8930  the coe∃cients of |εx|gn|gα+↓|g1, x|gn, |πand 
 8936  |εx|gn|gα_↓|g1 |πin |εv(x)q(x), |πnamely |εPa|β1v|βn|4α+↓|4P
 8940  |g2a|β2v|βn|βα_↓|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|4, 
 8941  a|β0v|βn|4α+↓|4Pa|β1v|βn|βα_↓|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|4, 
 8942  a|β0v|βn|βα_↓|β1|4α+↓|4Pa|β1v|βn|βα_↓|β2|4α+↓|1|1|¬O|4|¬O|4|
 8942  ¬O|4, |πeach of which is a multiple of |εP|g3. 
 8951  |πWe conclude from the _rst that |εp|gj|¬Da|β1, 
 8958  |πfrom the second that |εp|ur|πmin(|εk,2j)|)|)|¬Da|β0, 
 8963  |πthen from the third that |εP|¬Da|β0. |πHence 
 8970  |εP|¬Dr(x). |π[If |εm |πwere only |εn|4α+↓|41, 
 8976  |πthe best we could prove would be that |εp|ur|"pk/2|"P|)|) 
 8985  |πdivides |εr(x); |πe.g., consider |εu(x)|4α=↓|4x|g3|4α+↓|41
 8989  , v(x)|4α=↓|44x|g2|4α+↓|42x|4α+↓|41, r(x)|4α=↓|418. 
 8992  |πBy considering an algorithm for computing polynomial 
 8999  resultants, W. S. Brown has generalized this 
 9006  exercise in a di=erent way (to appear).]|'|H*?*?{U0}{H9L11M29}
folio 800 galley 13
 9013  58320#Computer Programming!(Knuth/A.-W.)!Ch. 
 9015  4!f. 800!g. 13c|'{A12}|≡1|≡5|≡.|4|9Let |εc|βi|βj|4α=↓|4a|βi|
 9019  β1a|βj|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|βi|βna|βj|βn; 
 9020  |πwe may assume that |εc|βi|βi|4|¬Q|40 |πfor 
 9026  all |εi. |πIf |εc|βi|βj|4|=|↔6α=↓|40 |πfor some 
 9032  |εi|4|=|↔6α=↓|4j, |πwe can replace row |εi |πby 
 9039  |ε(a|βi|β1|4α_↓|4ca|βj|β1,|4.|4.|4.|4,|4a|βi|βn|4α_↓|4ca|βj|
 9039  βn), |πwhere |εc|4α=↓|4c|βi|βj/c|βj|βj; |πthis 
 9043  does not change the value of the determinant, 
 9051  and it decreases the value of the upper bound 
 9060  we wish to prove, since |εc|βi|βi |πis replaced 
 9068  by |εc|βi|βi|4α_↓|4c|ur2|)ij|)/c|βi|βj. |πThese 
 9071  replacements can be done in a systematic way 
 9079  for increasing |εi |πand for |εj|4|¬W|4i, |πuntil 
 9086  |εc|βi|βj|4α=↓|40 |πfor all |εi|4|=|↔6α=↓|4j. 
 9090  |π(The latter algorithm is called ``Schmidt's 
 9096  orthogonalization process''; see |εMath. Annalen 
 9101  |≡6|≡3 (1907), 442.) |πThen det|ε(A)|g2|4α=↓|4det(|εAA|gT)|4
 9105  α=↓|4c|β1|β1|4.|4.|4.|4c|βn|βn.|'{A3}{H9L11M29}|π|≡1|≡6|≡.|4
 9106  |9Let |εf|1(x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|4g|βm(x|β2,|4.|4.|
 9107  4.|4,|4x|βn)x|urm|)1|)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4g|β0(x|
 9107  β2,|4.|4.|4.|4,|4x|βn), |πand let |εg(x|β2,|4.|4.|4.|4,|4x|β
 9110  n)|4α=↓|4g|βm(x|β2,|4.|4.|4.|4,|4x|βn)|g2|4α+↓|1|1|¬O|4|¬O|4
 9110  |¬O|1|1α+↓|4g|β0(x|β2,|4.|4.|4.|4,|4x|βn)|g2; 
 9111  |πthe latter is not identically zero. We have 
 9119  |εa|βN|4|¬E|4m(2N|4α+↓|41)|gn|gα_↓|g1|4α+↓|4(2N|4α+↓|41)b|βN
 9119  , |πwhere |εb|βN |πis the number of integer solutions 
 9128  of |εg(x|β2,|4.|4.|4.|4,|4x|βn)|4α=↓|40 |πwith 
 9131  variables bounded by |εN. |πHence lim|ε|βN|β|¬L|β|¬X|4a|βN/(
 9136  2N|4α+↓|41)|gn|4α=↓|4|πlim|ur|ε|)N|¬L|¬X|)|4b|βN/(2N|4α+↓|41
 9136  )|gn|gα_↓|g1, |πand this is zero by induction.|'
 9143  {A3}|≡1|≡7|≡.|4|9a) For convenience, let us describe 
 9149  the algorithm only for |εA|4α=↓|4|¬Ta,|4b|¬Y. 
 9154  |πThe hypotheses imply that deg(|εQ|β1U)|4α=↓|4|πdeg(|εQ|β2V
 9158  )|4|¬R|40, |πand deg(|εQ|β1)|4|¬E|4|πdeg(|εQ|β2). 
 9161  |πIf deg(|εQ|β1)|4α=↓|40, |πthen |εQ|β1 |πis 
 9166  must a nonzero rational number, so we set |εQ|4α=↓|4Q|β2/Q|β
 9174  1. |πOtherwise let |εQ|β1|4α=↓|4aQ|β1|β1|4α+↓|4bQ|β1|β2|4α+↓
 9177  |4r|β1, Q|β2|4α=↓|4aQ|β2|β1|4α+↓|4bQ|β2|β2|4α+↓|4r|β2, 
 9179  |πwhere |εr|β1 |πand |εr|β2 |πare rational numbers; 
 9186  it follows that|'{A9}|εQ|β1U|4α_↓|4Q|β2V|4α=↓|4a(Q|β1|β1U|4α
 9189  _↓|4Q|β2|β1V)|4α+↓|4b(Q|β1|β2U|4α_↓|4Q|β2|β2V)|4α+↓|4r|β1U|4
 9189  α_↓|4r|β2V.|;{A9}|πWe must have either deg(|εQ|β1|β1)|4α=↓|4
 9194  |πdeg(|εQ|β1)|4α_↓|41 |πor deg(|εQ|β1|β2)|4α=↓|4|πdeg(|εQ|β1
 9196  )|4α_↓|41. |πIn the former case, deg|ε(Q|β1|β1U|4α_↓|4Q|β2|β
 9201  1V)|4|¬W|4|πdeg(|εQ|β1|β1U), |πby considering 
 9204  the terms of highest degree which start with 
 9212  |εa; |πso we may replace |ε(Q|β1, Q|β2) |πby 
 9220  |ε(Q|β1|β2, Q|β2|β2) |πand repeat the process.|'
 9226  !!|1|1b) We may assume that deg(|εU)|4|¬R|4|πdeg(|εV). 
 9232  |πIf deg(|εR)|4|¬R|4|πdeg(|εV), |πnote that |εQ|β1U|4α_↓|4Q|
 9236  β2V|4α=↓|4Q|β1R|4α_↓|4(Q|β2|4α_↓|4Q|β1Q)V |πhas 
 9238  degree less than deg(|εV)|4|¬E|4|πdeg(|εQ|β1R), 
 9242  |πso we can repeat the process with |εU |πreplaced 
 9251  by |εR; |πwe obtain |εR|4α=↓|4Q|¬SV|4α+↓|4R|¬S, 
 9256  U|4α=↓|4(Q|4α+↓|4Q|¬S)V|4α+↓|4R|¬S, |πwhere deg(|εR|¬S)|4|¬W
 9258  |4|πdeg(|εR), |πso eventually a solution will 
 9264  be obtained.|'!!|1|1c) The algorithm of (b) gives 
 9272  |εV|β1|4α=↓|4UV|β2|4α+↓|4R, |πdeg(|εR)|4|¬W|4|πdeg|ε(V|β2); 
 9274  |πby homogeneity |εR|4α=↓|40 |πand |εU |πis homogeneous.|'
 9281  !!|1|1d) We may assume that deg|ε(V)|4|¬E|4|πdeg(|εU). 
 9287  |πIf deg(|εV)|4α=↓|40, |πset |εW|4|¬L|4U; |πotherwise 
 9292  use (c) to _nd |εU|4α=↓|4QV, |πso that |εQVV|4α=↓|4VQV, 
 9300  (QV|4α_↓|4VQ)V|4α=↓|40. |πThis implies that |εQV|4α=↓|4VQ, 
 9305  |πso we can set |εU|4|¬L|4V, V|4|¬L|4Q |πand 
 9312  repeat the process.|'!!|1|1For further details 
 9318  about the subject of this exercise, see P. M. 
 9327  Cohn, |εProc. Cambridge Phil. Soc. |≡5|≡7 (1961), 
 9334  18<30. |πThe considerably more di∃cult problem 
 9340  of characterizing |εall |πstring polynomials 
 9345  such that |εUV|4α=↓|4VU |πhas been solved by 
 9352  G. M. Bergman [Ph.D. thesis, Harvard University, 
 9359  1967].|'{A3}|≡1|≡8|≡.|4|9[P. M. Cohn, |εTransactions 
 9364  Amer. Math. Soc. |≡1|≡0|≡9 (1963), 332<356.]|'
 9370  {A3}{I3H}|π!!|1|1|≡C|≡1|≡.|9Set |εu|β1|4|¬L|4U|β1, 
 9372  u|β2|4|¬L|4U|β2, v|β1|4|¬L|4V|β1, v|β2|4|¬L|4V|β2, 
 9375  z|β1|4|¬L|4z|ur|↔0|)2|)|4|¬L|4w|β1|4|¬L|4w|ur|↔0|)2|)|4|¬L|4
 9375  1, z|ur|↔0|)1|)|4|¬L|4z|β2|4|¬L|4|¬L|4w|ur|↔0|)1|)|4|¬L|4w|β
 9376  2|4|¬L|40, n|4|¬L|40.|'{A3}|π!!|1|1|≡C|≡2|≡.|9(At 
 9379  this point the identities given in the exercise 
 9387  hold, and also |εu|β1v|β1|4α=↓|4u|β1v|β2; v|β2|4α=↓|40 
 9392  |πif and only if |εu|β1|4α=↓|40.) |πIf |εv|β2|4α=↓|40, 
 9399  |πthe algorithm terminates with gcrd(|εV|β1, 
 9404  V|β2)|4α=↓|4v|β1, |πlclm(|εV|β1, V|β2)|4α=↓|4z|ur|↔0|)1|)V|β
 9406  1|4α=↓|4|→α_↓z|ur|↔0|)2|)V|β2. (|πAlso by symmetry 
 9410  gcld(|εU|β1, U|β2)|4α=↓|4|πlclm(|εU|β1, U|β2)|4α=↓|4U|β1w|β1
 9412  |4α=↓|4|→α_↓U|β2w|β2.)|'{A3}|1|1!!|π|≡C|≡3|≡.|9Find 
 9414  |εQ |πand |εR |πsuch that |εv|β1|4α=↓|4Qv|β2|4α+↓|4R, 
 9420  |πwhere deg(|εR)|4|¬W|4|πdeg(|εv|β2). {H11}({H9}|πWe 
 9423  have |εu|β1(Qv|β2|4α+↓|4R)|4α=↓|4u|β2v|β2, |πso 
 9426  |εu|β1R|4α=↓|4(u|β2|4α_↓|4u|β1Q)v|β2|4α=↓|4R|¬Sv|β2.{H11}){H
 9426  9}|'{A3}!!|1|1|π|≡C|≡4|≡.|4|9Set (|εw|β1, w|β2, 
 9430  w|ur|↔0|)1|), w|ur|↔0|)2|), z|β1, z|β2, z|ur|↔0|)1|), 
 9435  z|ur|↔0|)2|), u|β1, u|β2, v|β1, v|β2)|4|¬L|4(w|ur|↔0|)1|)|4α
 9439  _↓|4w|β1Q, w|ur|↔0|)2|)|4α_↓|4w|β2Q, w|β1, w|β2, 
 9443  z|ur|↔0|)1|), z|ur|↔0|)2|), z|β1|4α_↓|4Qz|ur|↔0|)1|), 
 9446  z|β2|4α_↓|4Qz|ur|↔0|)2|), u|β2|4α_↓|4u|β1Q, u|β1, 
 9449  v|β2, v|β1|4α_↓|4Qv|β2) |πand |εn|4|¬L|4n|4α+↓|41. 
 9453  |πGo back to C2.|'|Hβ*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 9457